Pagini recente » Cod sursa (job #1358141) | Cod sursa (job #1088028) | Cod sursa (job #3227213) | Cod sursa (job #997627) | Cod sursa (job #1346311)
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
vector<int>L[100100],S[100100];
stack<int>s;
int n,m,i,j,a,b,nr,v[100100],x[100100],low[100100],niv[100100];
FILE *f,*g;
int minim(int a,int b){
if(a<b)
return a;
return b;
}
void dfs(int nod){
v[nod]=1;
a++;
low[nod]=niv[nod]=a;
x[nod]=1;
s.push(nod);
for(int i=0;i<L[nod].size();i++){
if( !v[ L[nod][i] ] ){
dfs( L[nod][i] );
low[nod] = minim( low[nod] , low[ L[nod][i] ] );
}
if( x[ L[nod][i] ] )
low[nod] = minim( low[nod] , low[ L[nod][i] ] );
}
if( low[nod]==niv[nod] ){
nr++;
do{
b=s.top();
s.pop();
x[b]=0;
S[nr].push_back(b);
}while(b!=nod);
}
}
int main(){
f=fopen("ctc.in","r");
g=fopen("ctc.out","w");
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++){
fscanf(f,"%d%d",&a,&b);
L[a].push_back(b);
}
a=0;
for(i=1;i<=n;i++){
if(v[i]==0)
dfs(i);
}
fprintf(g,"%d\n",nr);
for(i=1;i<=nr;i++){
for(j=0;j<S[i].size();j++){
fprintf(g,"%d ",S[i][j]);
}
fprintf(g,"\n");
}
fclose(f);
fclose(g);
return 0;
}