Pagini recente » Cod sursa (job #1973506) | Cod sursa (job #445767) | Cod sursa (job #2831963) | Cod sursa (job #604135) | Cod sursa (job #3197034)
#include <bits/stdc++.h>
#define FastIo() ios_base::sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
using namespace std;
const int nmax = 100005;
vector<int> adj[nmax], adj_rev[nmax],ctc[nmax];
vector<bool> used;
vector<int> post_order;
int n,m,x,y,nr_ctc;
void dfs1(int x){
used[x]=true;
for(int y:adj[x])
if(!used[y])
dfs1(y);
post_order.push_back(x);
}
void dfs2(int x){
used[x]=true;
ctc[nr_ctc].push_back(x);
for(int y: adj_rev[x])
if(!used[y])
dfs2(y);
}
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y;
adj[x].push_back(y);
adj_rev[y].push_back(x);
}
used.assign(n+1,false);
for(int i=1;i<=n;i++) if(!used[i]) dfs1(i);
used.assign(n+1,false);
for(int i=n-1;i>=0;--i){
x = post_order[i];
if(!used[x]){
nr_ctc++;
dfs2(x);
}
}
cout<<nr_ctc<<'\n';
for(int ind=1;ind<=nr_ctc;ind++){
int len = ctc[ind].size();
for(int i=0;i<len;i++)
cout<<ctc[ind][i]<<' ';
cout<<'\n';
}
return 0;
}