Algorithms/Kosarajus_SCC.cpp at master · Tejas988/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[100];
vector<int> transpose[100];
int n,m;
int vis[101];
stack<int> s;

void dfs(int src)
{
	vis[src]=1;
	for(auto x:adj[src])
	{
		if(vis[x])
			continue;
		dfs(x);
	}
	s.push(src);
	return;
}
void dfs2(int src)
{
	vis[src]=1;
	for(auto x:transpose[src])
	{
		if(vis[x])
			continue;
		dfs2(x);
	}
	cout<<src<<" ";
	return;
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("opts.txt", "w", stdout);
#endif
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		transpose[v].push_back(u);
	}
	for(int i=0;i<n;i++)
	{
		if(!vis[i])
			dfs(i);
	}
	for(int i=0;i<100;i++)
		vis[i]=0;
	while(!s.empty())
	{
		if(!vis[s.top()])
		{
			dfs2(s.top());
			cout<<endl;
		}
		s.pop();
	}
	return 0;

}