Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Kosaraju's SCC Algorithm
Bookmark
Input
3 SCCs
2 SCCs
Simple
Custom
n
=
8
,
edges
=
[[0,1],[1,2],[2,0],[3,4],[4,5],[5,3],[6,7],[7,6],[2,3],[5,6]]
Pass 1: DFS on Original Graph
0
1
2
3
4
5
6
7
Finish Stack:
(empty)
Legend:
Unvisited
In DFS
Finished
SCC Group
Pass 1: DFS on Original Graph
0
1
2
3
4
5
6
7
Finish Stack:
(empty)
Legend:
Unvisited
In DFS
Finished
SCC Group
Pass 1: DFS on Original Graph
0
1
2
3
4
5
6
7
Finish Stack:
(empty)
Legend:
Unvisited
In DFS
Finished
SCC Group
Pass 1: DFS on Original Graph
0
1
2
3
4
5
6
7
Finish Stack:
(empty)
Legend:
Unvisited
In DFS
Finished
SCC Group
Pass 1: DFS on Original Graph
0
1
2
3
4
5
6
7
Finish Stack:
(empty)
Legend:
Unvisited
In DFS
Finished
SCC Group
Pass 1: DFS on Original Graph
0
1
2
3
4
5
6
7
Finish Stack:
7
6
5
4
3
top
Legend:
Unvisited
In DFS
Finished
SCC Group
Pass 2: DFS on Transposed Graph
0
1
2
3
4
5
6
7
Finish Stack:
7
6
5
4
3
2
1
top
SCC IDs:
0
0
-
1
-
2
-
3
-
4
-
5
-
6
-
7
Legend:
Unvisited
In DFS
Finished
SCC Group
Pass 2: DFS on Transposed Graph
0
1
2
3
4
5
6
7
Finish Stack:
7
6
5
4
3
2
top
SCC IDs:
0
0
0
1
0
2
-
3
-
4
-
5
-
6
-
7
Legend:
Unvisited
In DFS
Finished
SCC Group
Pass 2: DFS on Transposed Graph
0
1
2
3
4
5
6
7
Finish Stack:
7
6
5
4
top
SCC IDs:
0
0
0
1
0
2
1
3
-
4
1
5
-
6
-
7
Legend:
Unvisited
In DFS
Finished
SCC Group
Pass 2: DFS on Transposed Graph
0
1
2
3
4
5
6
7
Finish Stack:
7
top
SCC IDs:
0
0
0
1
0
2
1
3
1
4
1
5
2
6
-
7
Legend:
Unvisited
In DFS
Finished
SCC Group
Pass 2: DFS on Transposed Graph
0
1
2
3
4
5
6
7
Finish Stack:
(empty)
SCC IDs:
0
0
0
1
0
2
1
3
1
4
1
5
2
6
2
7
Legend:
Unvisited
In DFS
Finished
SCC Group
algo
master
.
io
Step:
Start: Kosaraju's algorithm finds all Strongly Connected Components using two DFS passes
0 / 57
Input
3 SCCs
2 SCCs
Simple
Custom
n
=
8
,
edges
=
[[0,1],[1,2],[2,0],[3,4],[4,5],[5,3],[6,7],[7,6],[2,3],[5,6]]
0 / 57
algo
master
.
io
Step:
Start: Kosaraju's algorithm finds all Strongly Connected Components using two DFS passes
