Pagini recente » Cod sursa (job #2439217) | Cod sursa (job #324936) | Cod sursa (job #642303) | Cod sursa (job #2288375) | Cod sursa (job #2971892)
#include<bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,x,y,f[100001],nr;
vector<int> v1[100001],v2[100001],sol[100001];
stack<int> s;
void dfs1(int k)
{f[k]=1;
for(int i=0;i<v1[k].size();i++)
if(!f[v1[k][i]]) dfs1(v1[k][i]);
s.push(k);
}
void dfs2(int k)
{sol[nr].push_back(k);
f[k]=1;
for(int i=0;i<v2[k].size();i++)
if(!f[v2[k][i]]) dfs2(v2[k][i]);
}
void solve()
{
for(int i=1;i<=n;i++)
if(!f[i]) dfs1(i);
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)
{if(!f[s.top()]) nr++,dfs2(s.top());
s.pop();}
out<<nr<<'\n';
for(int i=1;i<=nr;i++)
{for(int j=0;j<sol[i].size();j++)
out<<sol[i][j]<<' ';
out<<'\n';
}
}
int main()
{in>>n>>m;
for(int i=1;i<=m;i++)
{in>>x>>y;
v1[x].push_back(y);
v2[y].push_back(x);}
solve();
return 0;
}