Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- typedef long long Long;
- #define MAX 100001
- #define PB push_back
- #define MP make_pair
- #define FF first
- #define SS second
- #define PII pair<int, int>
- #define VI vector<int>
- #define FOR(a, n) for(int i=a;i<n;i++)
- #define FORn(a, n) for(int i=a;i<=n;i++)
- #define mm(a, n) memset(a, n, sizeof(a))
- #define PF printf
- #define PC putchar
- #define GC getchar
- #define printCase cout<<"Case "<<i<<": "vagfol
- #define printCaseC PF("Case %d: ", i)
- #define II() ({int a; scanf("%d", &a); a;})
- #define LI() ({Long a; scanf("%I64d", &a); a;})
- #define DI() ({double a; scanf("%lf", &a); a;})
- #define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
- //double pi=atan(1)*4;
- using namespace std;
- vector<vector<int>> G(MAX), GT(MAX);
- int n, e;
- void Read()
- {
- cin>>n>>e;
- FOR(0, e)
- {
- int u, v;
- cin>>u>>v;
- G[u].PB(v);
- GT[v].PB(u);
- }
- }
- stack<int> s;
- int vis[MAX];
- void dfs(int u)
- {
- vis[u]=1;
- FOR(0, G[u].size())
- {
- int v=G[u][i];
- if(vis[v]==0)
- dfs(v);
- }
- s.push(u);
- }
- vector<int> res;
- void dfs2(int u)
- {
- vis[u]=1;
- res.PB(u);
- FOR(0, GT[u].size())
- {
- int v=GT[u][i];
- if(vis[v]==0)
- dfs2(v);
- }
- }
- void SCC()
- {
- FOR(0, n)
- {
- if(vis[i]==0)
- dfs(i);
- }
- mm(vis, 0);
- int cnt=0;
- vector<vector<int>> t;
- for(int i=1; !s.empty(); i++)
- {
- int u=s.top();
- s.pop();
- if(vis[u]==0)
- {
- dfs2(u);
- t.PB(res);
- res.clear();
- cnt++;
- }
- }
- FOR(0, t.size())
- {
- for(int j=0; j<t[i].size();j++)
- cout<<t[i][j]<<" ";
- cout<<endl;
- }
- cout<<"\nTotal: "<<cnt<<" strongly connected components\n";
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- #endif
- /* *******Bismillahir Rahmanir Rahim **** */
- // FastIO;
- Read();
- SCC();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement