Pagini recente » Cod sursa (job #740401) | Cod sursa (job #30358) | Cod sursa (job #1908977) | Cod sursa (job #910536) | Cod sursa (job #1607498)
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<algorithm>
#define MAXN 100005
FILE *f=fopen("ctc.in","r"), *g=fopen("ctc.out","w");
using namespace std;
vector <int> vec [MAXN];
vector <int> vecT[MAXN];
vector <int> c[MAXN];
int N, M, v[MAXN], nr, R;
bool viz[MAXN];
void Citire(){
int i, x, y;
fscanf(f,"%d %d\n",&N,&M);
for(i=1;i<=M;i++){
fscanf(f,"%d %d\n",&x,&y);
vec [x].push_back(y);
vecT[y].push_back(x);
}
}
void dfs( int k ){
int i;
viz[k] = 1;
for(i=0;i<vec[k].size();i++)
if( viz[ vec[k][i] ] == 0 )
dfs( vec[k][i] );
v[++nr] = k;
}
void dfsT( int k ){
int i;
c[R].push_back(k);
viz[k] = 1;
for(i=0;i<vecT[k].size();i++)
if( viz[ vecT[k][i] ] == 0 )
dfsT( vecT[k][i] );
}
void Rezolvare(){
int i, j;
nr = 0;
for(i=1;i<=N;i++)
if( viz[i] == 0 )
dfs(i);
memset(viz,0,sizeof(viz));
R = 0;
for(i=N;i>=1;i--)
if( viz[v[i]] == 0 ){
R++;
dfsT( v[i] );
}
fprintf(g,"%d\n",R);
for(i=1;i<=R;i++){
for(j=0;j<c[i].size();j++)
fprintf(g,"%d ",c[i][j]);
fprintf(g,"\n");
}
}
int main(){
Citire();
Rezolvare();
return 0;
}