Pagini recente » Cod sursa (job #2414371) | Cod sursa (job #1734153) | Cod sursa (job #1602373) | Cod sursa (job #3236946) | Cod sursa (job #919486)
Cod sursa(job #919486)
#include <stdio.h>
#include <vector>
#define MAXN 100001
int n,m;
std::vector<int> normal[MAXN];
std::vector<int> transp[MAXN];
bool viz[MAXN];
int nr=0;
std::vector<int> oups;
void DFS(int x){
viz[x]=true;
for (int i=0;i<normal[x].size();i++){
if (!viz[normal[x][i]]){
DFS(normal[x][i]);
}
}
oups.push_back(x);
}
void DFST(int x){
viz[x]=false;normal[nr].push_back(x);
for (int i=0;i<transp[x].size();i++){
if (viz[transp[x][i]]){
DFST(transp[x][i]);
}
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for (int i=1;i<=m;i++){
int x,y;
scanf("%d %d",&x,&y);
normal[x].push_back(y);
transp[y].push_back(x);
}
for (int i=1;i<=n;i++){
if (!viz[i]){
DFS(i);
}
}
for (int i=oups.size();i>=0;i--){
if (viz[oups[i]]){
nr++;
normal[nr].clear();
DFST(oups[i]);
}
}
printf("%d\n",nr);
for (int i=1;i<=nr;i++){
for (int j=0;j<normal[i].size();j++)
printf("%d ",normal[i][j]);
printf("\n");
}
return 0;
}