Jim_Moriarty_'s blog

SCCs
By Jim_Moriarty_, history, 5 years ago, In English

Can two strongly connected components overlap ?

I read somewhere that they can't.

But at the same time I encountered a problem https://www.hackerearth.com/practice/algorithms/graphs/strongly-connected-components/tutorial/

problem is at the bottom of the page Consider the example testcase given - 5 6

1 4

1 3

2 4

3 4

4 5

5 1

I found manually that there are two SCCs -(1, 3, 4, 5) and (2) So the answer should be zero. But it's given as -3. So am I not understanding something about SCC or the answer given is wrong? Please help.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I think the answer given is wrong. Because the SCCs found by you are correct.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You are given a graph with N nodes and M directed edges. Find C-D

Where,

C Sum of number of nodes in all Strongly Connected Components with odd number of nodes.

D Sum of number of nodes in all Strongly Connected Components with even number of nodes.

The question asks you to find this. So odd comp size you got is 1 and even comp size you got is 4.

Hence 1-4 = -3.

→ Reply