Pagini recente » Cod sursa (job #74) | Cod sursa (job #2918078) | Cod sursa (job #3259414) | Cod sursa (job #1779719) | Cod sursa (job #1609817)
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
vector<int>L[100100],sol[100100];
stack<int>s;
int n,m,a,b,i,j,nr,v[100100],low[100100],niv[100100],x[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++;
s.push(nod);
x[nod]=1;
niv[nod]=low[nod]=a;
for(int i=0;i<L[nod].size();i++){
if( v[ L[nod][i] ] == 0 ){
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();
sol[nr].push_back(b);
x[b]=0;
}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<sol[i].size();j++){
fprintf(g,"%d ",sol[i][j]);
}
fprintf(g,"\n");
}
fclose(f);
fclose(g);
return 0;
}