Pagini recente » Cod sursa (job #2839623) | Cod sursa (job #2457112) | Cod sursa (job #2511784) | Cod sursa (job #1991547) | Cod sursa (job #424306)
Cod sursa(job #424306)
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define FIN "ctc.in"
#define FOUT "ctc.out"
#define NMAX 100005
using namespace std;
vector<int> Gi[NMAX],Gt[NMAX],rez[NMAX],aux;
int n,m,COLOR[NMAX];
void DFS(vector<int> G[NMAX],int nod,int C,vector<int> & aux )
{COLOR[nod]=C;
vector<int>::iterator i;
for(i=G[nod].begin();i!=G[nod].end();i++)
if(COLOR[*i]==C-1)
DFS(G,*i,C,aux);
aux.push_back(nod);
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{int x,y;
scanf("%d %d",&x,&y);
Gi[x].push_back(y);
Gt[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(COLOR[i]==0) DFS(Gi,i,1,aux);
vector<int>::iterator i;
int nr=0;
for(;aux.size();aux.pop_back())
if(COLOR[aux.back()]!=2)
{nr++;
DFS(Gt,aux.back(),2,rez[nr]);
}
printf("%d\n",nr);
for(int i=1;i<=nr;i++)
{vector<int>::iterator it;
for(it=rez[i].begin();it!=rez[i].end();it++)
printf("%d ",*it);
printf("\n");
}
return 0;
}