Pagini recente » Cod sursa (job #1989177) | Cod sursa (job #41478) | Cod sursa (job #2821605) | Cod sursa (job #2529720) | Cod sursa (job #1314710)
#include <cstdio>
#include <vector>
#include <cstring>
#define nmax 100010
using namespace std;
vector <int> a[nmax],aT[nmax],sol[nmax];
FILE *f1,*f2;
int n,m,u,v,i,j,s[nmax],k,nr;
int use[nmax];
void DFS(int nod)
{int i;
use[nod]=1;
for (i=0;i<(int)a[nod].size();i++)
if (!use[a[nod][i]]) DFS(a[nod][i]);
s[++k]=nod;
}
void DFS2(int nod)
{int i;
use[nod]=1;
sol[nr].push_back(nod);
for (i=0;i<(int)aT[nod].size();i++)
if (!use[aT[nod][i]]) DFS2(aT[nod][i]);
}
int main()
{f1 = fopen("ctc.in","r");
f2 = fopen("ctc.out","w");
fscanf(f1,"%d%d",&n,&m);
for (i=1;i<=m;i++) {fscanf(f1,"%d%d",&u,&v);a[u].push_back(v);aT[v].push_back(u);}
for (i=1;i<=n;i++)
if (!use[i]) DFS(i);
memset(use,0,sizeof(use));
for (i=n;i>=1;i--)
if (!use[s[i]])
{nr++;
DFS2(s[i]);
}
fprintf(f2,"%d\n",nr);
for (i=1;i<=nr;i++)
{for (j=0;j<(int)sol[i].size();j++) fprintf(f2,"%d ",sol[i][j]);
fprintf(f2,"\n");
}
fclose(f1);
fclose(f2);
}