Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- const int N = 100005;
- int n,m,tplt=0;
- vector<vector<int>> a,b;
- stack<int> s;
- vector<bool> visited;
- vector<int> res[N];
- void dfs1(int u)
- {
- visited[u]=true;
- for(int i = 0; i<a[u].size(); ++i)
- {
- if (!visited[a[u][i]]) {
- dfs1(a[u][i]);
- }
- }
- s.push(u);
- }
- void dfs2(int u, int d)
- {
- visited[u]=true;
- for(int i = 0; i<b[u].size(); ++i)
- {
- int v = b[u][i];
- if (!visited[v])
- {
- res[d].push_back(v);
- dfs2(v,d);
- }
- }
- }
- void sol()
- {
- for(int i=1; i<=n; ++i) if(!visited[i]) dfs1(i);
- for(int i=1; i<=n; ++i) visited[i]=false;
- while (!s.empty())
- {
- int z = s.top(); s.pop();
- if (!visited[z])
- {
- ++tplt;
- res[tplt].push_back(z);
- dfs2(z,tplt);
- }
- }
- cout << tplt << endl;
- for(int i=1; i<=tplt; ++i)
- {
- cout << res[i].size() << endl;
- for(int v : res[i])
- {
- cout << v << " ";
- }
- cout << endl;
- }
- }
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- //freopen("sconnect.inp","r",stdin);
- cin >> n >> m;
- a.resize(n+1,vector<int>(0));
- b.resize(n+1,vector<int>(0));
- visited.resize(n+1,false);
- for(int i=1; i<=m; ++i)
- {
- int u,v;
- cin >> u >> v;
- a[u].push_back(v);
- b[v].push_back(u);
- }
- sol();
- return 0;
- }
Add Comment
Please, Sign In to add comment