Pagini recente » Cod sursa (job #430773) | Cod sursa (job #211789) | Cod sursa (job #2542904) | Cod sursa (job #771903) | Cod sursa (job #1868361)
#include <cstdio>
#include <vector>
#define NMax 100000
using namespace std;
vector<int> sol[NMax+1];
vector<int> A[NMax+1];
vector<int> B[NMax+1];
char deja[NMax+1];
int stiva[NMax+1];
int res,vf;
void DFS(int x)
{
int y;
deja[x] = 1;
for(int i = 0; i < A[x].size(); ++i)
{
y = A[x][i];
if(!deja[y]) DFS(y);
}
stiva[++vf] = x;
}
void DFS2(int x)
{
int y;
deja[x] = 0;
for(int i = 0; i < B[x].size(); ++i)
{
y = B[x][i];
if(deja[y]) DFS2(y);
}
sol[res].push_back(x);
}
int main(){
FILE* fin = fopen("ctc.in","r");
FILE* fout = fopen("ctc.out","w");
int i,j,x,y,N,M;
fscanf(fin,"%d %d",&N,&M);
for(i = 1; i <= M; ++i)
{
fscanf(fin,"%d %d",&x,&y);
A[x].push_back(y);
B[y].push_back(x);
}
for(i = 1; i <= N; ++i)
if(!deja[i]) DFS(i);
for(i = N; i >= 1; --i)
if(deja[ stiva[i] ])
{
++res;
DFS2(stiva[i]);
}
fprintf(fout,"%d\n",res);
for(i = 1; i <= res; ++i)
{
for(j = 0; j < sol[i].size(); ++j) fprintf(fout,"%d ",sol[i][j]);
fprintf(fout,"\n");
}
return 0;
}