Pagini recente » Cod sursa (job #1864844) | Cod sursa (job #1965185) | Cod sursa (job #223642) | Cod sursa (job #59420) | Cod sursa (job #631810)
Cod sursa(job #631810)
#include<cstdio>
#include<vector>
using namespace std;
int n,m,x,y,T,i,COMP,viz[100010],f[100010];
vector<int> G[100010],GT[100010],comp[100010];
vector<int> Q;
void read(),solve(),dfs(int),dfs1(int);
int main()
{
read();
solve();
return 0;
}
void read()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
GT[y].push_back(x);
}
}
void solve()
{
vector<int>::reverse_iterator rit;
for(i=1;i<=n;i++)
{
if(viz[i]!=1)
dfs(1);
}
/* for(iit=Q.begin();iit!=Q.end();iit++)
printf(" %d ",*iit);
printf("\n");
for(i=1;i<=n;i++)printf(" %d ",f[i]);*/
for(rit=Q.rbegin();rit!=Q.rend();rit++)
{
if(viz[*rit]!=2)
{
COMP++;
dfs1(*rit);
}
}
vector<int>::iterator it;
printf("%d\n",COMP);
for(i=1;i<=COMP;i++)
{
for(it=comp[i].begin();it!=comp[i].end();it++)printf("%d ",*it);
printf("\n");
}
}
void dfs(int nod)
{
vector<int>::iterator it;
viz[nod]=1;
for(it=G[nod].begin();it!=G[nod].end();it++)
{
if(viz[*it]!=1)
dfs(*it);
}
++T;
Q.push_back(nod);
f[nod]=T;
}
void dfs1(int nod)
{
vector<int>::iterator it;
viz[nod]=2;
for(it=GT[nod].begin();it!=GT[nod].end();it++)
{
if(viz[*it]!=2)
dfs1(*it);
}
comp[COMP].push_back(nod);
}