# Strongly connected components in graph

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)

• Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Oct 25 '14 at 8:29
• You got the SCC of $G$ wrong. – FrankW Oct 25 '14 at 8:30

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)$.