Pagini recente » Cod sursa (job #1658413) | Cod sursa (job #757323) | Cod sursa (job #1624733) | Cod sursa (job #2805444) | Cod sursa (job #423738)
Cod sursa(job #423738)
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define FIN "ctc.in"
#define FOUT "ctc.out"
#define NMAX 100005
#define MMAX 200004
using namespace std;
vector <int> Gn[NMAX],Gt[NMAX],REZ[NMAX],adj;
int COLOR[NMAX],n,m,x,y,nr;
void DFS(vector<int> *graf , int nod , int Col , vector<int> &rez )
{vector<int>::iterator it;
COLOR[nod]=Col;
for ( it=graf[nod].begin() ; it!=graf[nod].end() ; it++ )
if(COLOR[*it]==Col-1)
DFS(graf,*it,Col,rez);
rez.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++)
{scanf("%d %d",&x,&y);
Gn[x].push_back(y);
Gt[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(COLOR [ i ]== 0 )
{nr++;
adj.clear();
DFS(Gn,i,1,adj);
DFS(Gt,i,2,REZ[nr]);
vector<int>::iterator it;
for(it=adj.begin();it!=adj.end();it++)
if(COLOR[*it]==1) COLOR[*it]=0;
}
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;
}