If you want to make money online : Register now

# [Solved]: Strongly connected components in graph

, ,
Problem Detail:

Statement:SCC in G is same as Rev(G)

Ex:Consider the following graph g

0->1

1->2

2->4

3->1

4->3

The strong components set would be S={0,1,2,3,4}

If I reverse the above graph (i.e)

1->0

1->3

2->1

3->4

4->2

Then the strong components set would be S'1={0} S'2={1,2,3,4}

Which shows that strong components in G is not same as strong components in Rev(g)

In a strongly connected component of a graph, all nodes of the SCC must be reachable from all other nodes in the SCC. So, if \$x\$ and \$y\$ are nodes of the SCC, then there is a path from \$x\$ to \$y\$ and a path from \$y\$ to \$x\$. Clearly, if we reverse all edges in the graph, then there is still a path from \$x\$ to \$y\$ (the old path from \$y\$ to \$x\$) and still a path from \$y\$ to \$x\$ (the old path from \$x\$ to \$y\$).

Your mistake in determining the SCCs of the first graph \$G\$: there is no edge going into node \$0\$, thus \$0\$ is not reachable from any of the other nodes. Therefore the SCCs of \$G\$ are \$\{0\}\$ and \$\{1,2,3,4\}\$, which are also the SCCs of \$\mathit{Rev}(G)\$.