Graph-Theory/Strongly_connected_components.cpp at master · bishworup11/Graph-Theory · 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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
#define ll long long

#define ff        first
#define ss        second
#define sz(x)    (int) x.size()
#define endl      '\n'
#define pb        push_back
#define all(v)    v.begin(), v.end()
#define     YES   printf("YES\n")
#define     Yes   printf("Yes\n")
#define     NO    printf("NO\n")
#define     No    printf("No\n")

#define     mem(a)      memset(a , 0 ,sizeof a)
#define     memn(a)     memset(a , -1 ,sizeof a)

const int lim = 1048576;
const int M    = 1e9 + 7;
const int Inf           = (int)2e9 + 5;
const ll  Lnf           = (ll)2e18 + 5;
const int N             = 5e5 + 5;
const int NN            = 1e6 + 5;

#define error(args...) {vector<string>_v=split(#args,',');err(_v.begin(),args);cout<<endl;}
vector<string> split(const string &s, char c) {vector<string>v; stringstream ss(s); string x; while (getline(ss, x, c))v.emplace_back(x); return move(v);} void err(vector<string>::iterator it) {}
template<typename T, typename... Args>void err(vector<string>::iterator it, T a, Args...args) {cout << it->substr((*it)[0] == ' ', it->length()) << " = " << a << " "; err(++it, args...);}

//tech dose//
std::vector<int>g[N], rev[N];
int n, m;
void dfs1(int node,vector<bool>&visited,stack<int>&mystack)
{
    visited[node]=true;
    for (int i = 0; i <g[node].size(); ++i)
    {
    	int v=g[node][i];
    	if(!visited[v])
    	{
    		dfs1(v,visited,mystack);
    	}
    }
    mystack.push(node);
    return ;
}

void dfs2(int node,vector<bool>&visited)
{
	visited[node]=true;
	cout<<node<<" ";
	for (int i = 0; i <rev[node].size(); ++i)
	{  int v=rev[node][i];
		if(!visited[v])
		{
			dfs2(v,visited);
		}
	}

	return;
}

void scc()
{
	stack<int>mystack;
	std::vector<bool>visited(n+5, false);
	for (int i = 1; i <= n; ++i)
	{  if(!visited[i])
		dfs1(i, visited, mystack);
	}

    for (int i = 0; i <=n; ++i)visited[i]=false;
    cout<<"connected components are \n";

    while(!mystack.empty())
    {
    	int v=mystack.top();
    	//error(v);
    	mystack.pop();
    	if(!visited[v])
    	{
    		dfs2(v,visited);
    		cout<<endl;
    	}
    }

}

int solve()
{

	cin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		rev[v].push_back(u);
	}

	scc();


	return 0;
	//error();
}
int main() {

	//ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int test = 1, tc = 0;
	//cin >> test;
	while (test--) {
		//printf("Case %d: ", ++tc);
		solve();
	}

	return 0;
}