Log In
44 votes

Let $G=(V,E)$ be a directed graph where $V$ is the set of vertices and $E$ the set of edges. Then which one of the following graphs has the same strongly connected components as $G$ ?

  1. $G_1$ = $(V,E_1)$ where $E_1 = \left\{(u,v) \mid (u,v) \notin E\right\}$
  2. $G_2$ = $(V,E_2)$ where $E_2 = \left\{(u,v) \mid (v,u) \in E \right\}$
  3. $G_3$ = $(V,E_3)$ where $E_3 = \{(u,v) \mid$ there is a path of length $\leq2$ from $u$ to $v$ in $E\}$
  4. $G_4$ = $(V_4,E)$ where $V_4$ is the set of vertices in $G$ which are not isolated
in DS
recategorized by
Both B & C seem true.

Both Gate official key & answers here say "B" is the answer than why "C" is mentioned as answer down in this page.

Updated ..that was a typo
What is strongly connected component?

strongly connected component means, if there is a path exists between all the vertices of the component

V4 is the set of vertices that are not isolated thus which are connected in G, so wouldn't it provide the same set of strongly connected components as G.
Is it safe to say, G1 is the compliment of G?

3 Answers

61 votes
Best answer

(A) is false. Consider just two vertices connected to each other. So, we have one SCC. The new graph won't have any edges and so $2$ SCC.

(B) is true. In a directed graph an SCC will have a path from each vertex to every other vertex. So, changing the direction of all the edges, won't change the SCC.

(D) is false. Consider any graph with isolated vertices- we loose those components.

(C) is a bit tricky. Any edge is a path of length $1$. So, the new graph will have all the edges from old one. Also, we are adding new edges $(u,v)$. So, does this modify any SCC? No, because we add an edge $(u,v)$, only if there is already a path of length $<= 2$ from $u$ to $v$- so we do not create a new path.  So, both (B) and (C) must answer, though GATE key says only B.

edited by
fully connected will not work for (D).
Yes, Missed the "not". Corrected now..
even in case of D, the number of strongly connected components will be same, right ?

@Arjun sir... C to A there is no edge so path length is 0 .. if we add edge wil generate new stongly connected component...same way C TO B also generates new strongly connected component.. by this can we make c option as false...

If path length is allowed to be 0, then all shortest path algorithms will fail
yup got it..
Doubt: In option A, are we considering an ordered pair between two vertices as an edge, or an edge doesnot have any order here?

@Arjun Sir, what would have been about option (C) if the question was asked like this :

Guaranteed to have same strongly connected components as G

Sir for option (B), the structure of the graph will change due to change of direction...they have asked for the SAME strongly connected component as G, then how will (B) be the answer?

Consider a cyclic graph with 3 vertices as G.  Now, if we reverse the edges in G2, its strongly connected will it be same as G?
Even if we reverse the direction of edges its going to be the same strongly connected component.

I think for more clarity you can refer CLRS on "Finding Strongly connected components in a graph using DFT"

Is this ex proof c option wrong ?


How are you creating a path from D  To C ?

There is a path from C to D .And From D to E So, there can be a path from C to E.

No path from D to C .

It is a directed graph you cannot do like this.
they said if there is path <=2 then uv will be edge in v, e3 graph ...rt
Yes but you tell me where is the path from D to C in original graph??
i got it thanks

For option C, path of len<=2 i.e. path of len zero is also to be considered.

Say A-B-C is one SCC component and D(isolated vertex) is another SCC. So in G there are two SCC.

But in G3{ V,E3 }, this vertex D will be connected with bidirectional edges to all A , B, C reducing no. of SCC by 1.

New Doc 2017-10-22.jpg


yes , i think this one proves C also wrong
@arjun sir

When the original graph has a strongly connected component which includes isolated vertex

then option C fails

because length <=2 and therefore also includes path length =0 and will give rise to a path which is not there in the original, thereby changing the number of strongly connected components

@A_i_$_h : If the oath do not exist then path length would be undefined/infinity. If we take zero then shortest path wont work.

Remember ,if we apply dijkstra/bellman ford on graph and it has isolated vertex,then path would be not defined.If you define it as zero then it would report 0 length path,which is wrong


yea valid one :)

@From cormen


@Arjun Sir
Pls check: If there is a path of length ≤ 1 from u to v in E, still the SCC will be same as in G right?


@Ayush Upadhyaya @Arjun sir

G3 = (V,E3) where E3={(u,v)∣ there is a path of length ≤2  from u to v in E}

What is options are like 

G3 = (V,E3) where E3 = {(u,v) such that there is A PATH from u to v in E}

as in original G ..u and v are connected in G3 also they will be connected and does it add any new SCCs in G3 ???


yes of course. SSC won't change here..
0 can C true they already mentioned it is directed graph....if you add atmost 2 length path from U to V  then how can you say that it is also V to U.....if it is corrected then i am missing something. 


 Arjun sir...

the explaination you have given in proving the option A) is false is true iff G is an undirected graph...

But G is directed..

i am not saying option A) is the answer...its obviously B)..but the reason you have written for A) is wrong i think..






Arjun sir's explanation is correct, he has considered a graph which is different from your example, in which there is an edge from vertex 1 to vertex 2, as well as from 2 to 1, that's how there's only 1 SCC in G, and then applying option A gives 2 SCCs

Also, even a directed graph can have 2 edges between 2 vertices (from 1 to 2 and from 2 to 1). Even though it's equivalent to an undirected graph with vertices 1 and 2, it can still be considered as a directed graph.

3 votes

G(V, E) is a directed graph.
→ It strongly connected.
(A) G1=(V,E1) where E1={(u,v)|(u,v)∉E}
If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.
(B) G2=(V,E2 )where E2={(u,v)│(v,u)∈E}
Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.
Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.
(C) G3=(V,E3) where E3={(u,v)|there is a path of length≤2 from u to v in E}
This can also be true.

Both from each vertex to other vertex is also exists. So it is also strongly connected graph.
(D) G4=(V4,E) where V4 is the set of vertices in G which are not isolated.
If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component
then no. of SCC = x + 1
G4 contain only ‘1’ component, which is not same as G.

reshown by
–2 votes
A. Can be eliminated as if the component is strongly connected in E then it will not be strongly connected in E's complement.

B.This is reversing the directions of the edges. When a triangle is considered for instance, where the directions are such that it will form a cycle, on reversing these directions the triangle will no more be strongly connected as there will be a vertex from which we cant reach out to any other vertex.

C.This is mostly the answer as according to the condition the number of edges in E3 will be those present in E and also additional edges which connect all U to all V such that UV<=2. Hence the connected component will stay connected.

D.V4 has only single vertices ,i.e those which were isolated in G and no edges will be present between them.
Your counter example for (B) is not correct. When we reverse the direction of all edges, it again forms a cycle rt- in reverse direction?
doubt: (D) also seems correct.. V4 is set of of vertices which in G which are not isolated. Anyways those isolated vertices makes no contribution in strongly connected component.. so even if we choose  those or not the graph gonna  have the same connected component as that of G... Isn't it..??

So (B) and (D) both seems correct..??
As per official answer GATE 2014 answer key it is B. Also counter example for B is incorrect.
Consider the graph G to be containing 3 nodes, wherein we have 2 edges - 1 between the 1st and the 2nd nodes and the other edge between the 2nd and the 3rd nodes.

Now, for (C), we'll get a graph wherein, an edge has been constructed between the 1st and the 3rd nodes, thus we will be getting a SCC in this modified graph, whereas we didn't have any in the origina graph.

Hence, (C) can be eliminated.

Related questions

25 votes
3 answers
Consider a hash table with $9$ slots. The hash function is $h(k)= k \mod 9$. The collisions are resolved by chaining. The following $9$ keys are inserted in the order: $5, 28, 19, 15, 20, 33, 12, 17, 10$. The maximum, minimum, and average chain lengths in the hash table, respectively, are $3, 0,$ and $1$ $3, 3,$ and $3$ $4, 0,$ and $1$ $3, 0,$ and $2$
asked Sep 28, 2014 in DS jothee 4.2k views
60 votes
10 answers
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly $4$ nodes is $O(n^a\log^bn)$. Then the value of $a+10b$ is __________.
asked Sep 26, 2014 in DS jothee 11k views
46 votes
8 answers
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$. W=$\begin{bmatrix} 0&2 &8 &5 \\ 2&0 &5 &8 \\ 8&5 &0 &x \\ 5& 8 &x &0 \end{bmatrix}$ The largest possible integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________.
asked Feb 12, 2016 in DS Sandeep Singh 12.1k views
0 votes
2 answers
$S_{1}$ : I teach algorithms and maths. $S_{2}$ : My professor teaches maths, electronics and computer science. $S_{3}$ : I have a student of maths. $S_{4}$ : Algorithm is a part of computer science. $S_{5}$ : Maths students know computer science. What would ... /relationships amongst the entities/actors as expressed in the sentences $S_{1}$ to $S_{5}$ above ? $2$ $3$ $4$ None of these
asked Sep 15, 2016 in DS makhdoom ghaya 433 views