Pagini recente » Cod sursa (job #930136) | Cod sursa (job #966028) | Cod sursa (job #626675) | Cod sursa (job #2524567) | Cod sursa (job #2280229)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,a,b,r,v[100001];
vector <int> g[100001];
vector <int> gt[100001];
vector <int> ctc[100001];
stack <int> s;
int dfs(int k)
{ vector <int>::iterator it;
v[k]=1;
for(it=g[k].begin();it!=g[k].end();it++)
{ int vf;
vf=(*it);
if(v[vf]==0)
dfs(vf);
}
s.push(k);
}
int dfst(int k)
{ vector <int>::iterator it;
v[k]=1;
ctc[r].push_back(k);
for(it=gt[k].begin();it!=gt[k].end();it++)
{ int vf;
vf=(*it);
if(v[vf]==0)
dfst(vf);
}
s.push(k);
}
int main()
{ in>>n>>m;
for(int i=1;i<=m;i++)
{ in>>a>>b;
g[a].push_back(b);
gt[b].push_back(a);
}
for(int i=1;i<=n;i++)
if(v[i]==0)
dfs(i);
for(int i=1;i<=n;i++)
v[i]=0;
while(!s.empty())
{ int vf;
vf=s.top();
s.pop();
if(v[vf]==0)
{ r++;
dfst(vf);
}
}
out<<r<<'\n';
for(int i=1;i<=r;i++)
{ for(auto nod:ctc[i])
out<<nod<<' ';
out<<'\n';
}
in.close();
out.close();
return 0;
}