Pagini recente » Cod sursa (job #1453312) | Cod sursa (job #2802289) | Cod sursa (job #1296791) | Cod sursa (job #2211031) | Cod sursa (job #293969)
Cod sursa(job #293969)
#include<stdio.h>
#include<vector>
#include<algorithm>
#define MAXN 100001
using namespace std;
int n,m,i,nrc,N,j;
int coada[MAXN],v1[MAXN],v2[MAXN];
vector <int> a[MAXN],at[MAXN],ctc[MAXN];
void dfs(int nod)
{
int i;
v1[nod]=1;
for(i=0;i<a[nod].size();i++)
if(!v1[a[nod][i]])
dfs(a[nod][i]);
coada[++N]=nod;
}
void dfst(int nod)
{
int i;
v2[nod]=1;
ctc[nrc].push_back(nod);
for(i=0;i<at[nod].size();i++)
if(!v2[at[nod][i]])
dfst(at[nod][i]);
}
int main(void)
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
int x,y;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[x].push_back(y);
at[y].push_back(x);
}
for(i=1;i<=n;i++)
if(!v1[i])
dfs(i);
for(i=N;i>=1;i--)
if(!v2[coada[i]])
{
nrc++;
dfst(coada[i]);
}
printf("%d\n",nrc);
for(i=1;i<=nrc;i++)
{
for(j=0;j<ctc[i].size();j++)
printf("%d ",ctc[i][j]);
printf("\n");
}
return 0;
}