Pagini recente » Cod sursa (job #1466840) | Cod sursa (job #1791185) | Cod sursa (job #399744) | Cod sursa (job #1053353) | Cod sursa (job #3248869)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int> v[100001],invv[100001],comp[100001];
vector<int> ordine;
int viz[100001],n;
void dfs1(int nod){
int i;
viz[nod]=1;
for(i=0;i<v[nod].size();i++){
if(viz[v[nod][i]]) continue;
dfs1(v[nod][i]);
}
ordine.push_back(nod);
}
void dfs2(int nod,int comp_curenta){
int i;
viz[nod]=1;
for(i=0;i<invv[nod].size();i++){
if(viz[invv[nod][i]]) continue;
dfs2(invv[nod][i],comp_curenta);
}
comp[comp_curenta].push_back(nod);
}
void reset(){
int i;
for(i=0;i<=n;i++) viz[i]=0;
}
int main()
{
int m,i,j,a,b,cnt=0;
cin>>n>>m;
for(i=1;i<=m;i++){
cin>>a>>b;
v[a].push_back(b);
invv[b].push_back(a);
}
for(i=1;i<=n;i++){
if(!viz[i]) dfs1(i);
}
reverse(ordine.begin(),ordine.end());
reset();
for(i=0;i<n;i++){
if(viz[ordine[i]]==0){
cnt++;
dfs2(ordine[i],cnt);
}
}
cout<<cnt<<"\n";
for(i=1;i<=cnt;i++){
for(j=0;j<comp[i].size();j++) cout<<comp[i][j]<<" ";
cout<<"\n";
}
return 0;
}