Pagini recente » Cod sursa (job #1356620) | Cod sursa (job #2123205) | Cod sursa (job #2661269) | Cod sursa (job #2616891) | Cod sursa (job #1607542)
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stack>
#define MAXN 100005
FILE *f=fopen("ctc.in","r"), *g=fopen("ctc.out","w");
using namespace std;
vector <int> v[MAXN], c[MAXN];
stack <int> ST;
int N, M, R=0, t=0, low[MAXN], niv[MAXN];
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);
v[x].push_back(y);
}
}
void dfs( int k ){
int i, NEWk, x;
t++;
viz[k] = 1;
low[k] = niv[k] = t;
ST.push(k);
for(i=0;i<v[k].size();i++){
NEWk = v[k][i];
if( viz[ NEWk ] == 0 ){
dfs(NEWk);
low[k] = min( low[k], low[NEWk] );
}
else{
low[k] = min( low[k], niv[NEWk] );
}
}
if( niv[k] == low[k] ){
R++;
do{
x =ST.top();
c[R].push_back(x);
ST.pop();
} while( k != x );
}
}
int main(){
Citire();
for(int i=1;i<=N;i++)
if( viz[i] == 0 )
{
t=0;
dfs(i);
}
fprintf(g,"%d\n",R);
for(int i=1;i<=R;i++){
for(int j=0;j<c[i].size();j++)
fprintf(g,"%d ",c[i][j]);
fprintf(g,"\n");
}
return 0;
}