A **strongly connected component** of a directed graph is a maximal **strongly connected subgraph**

1. svw

2. qty

3. xz

4. r

5. u

The Gateway to Computer Science Excellence

+1 vote

+1

A **strongly connected component** of a directed graph is a maximal **strongly connected subgraph**

1. svw

2. qty

3. xz

4. r

5. u

+1

https://gateoverflow.in/3589/gate2006-it-46

you can check the above question for more info how to find strongly connected components using algorithm or intuitively.

+2 votes

+1

Using Kosaraju's Algorithm

1> step find the DFS of G.and store their finishing time

2>compute Transpose of G and after that perform DFS of Transpose of G and then perform then perform the traversal in such a way that for each node the adjacent nodes should be visited in decreasing order of their finishing time.

And we are comparing the number of connected components in the 2 graphs G and $G^{T}$ right??

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,523 answers

195,608 comments

101,286 users