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.
I think the answer given is wrong. Because the SCCs found by you are correct.
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.
Ohw! Thanks! I didn't understand the question properly.