Pagini recente » Cod sursa (job #436056) | Statistici Iantoc Alexandru (ipikachus) | Istoria paginii utilizator/radu.ghita | Cod sursa (job #262574) | Cod sursa (job #713984)
Cod sursa(job #713984)
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
int N,M,C,Ind;
int index[100100],lowL[100100];
vector<int> nr[100100],comp[100100];
stack<int> S;
char viz[100100],in_S[100100];
void DF(int x){
if(viz[x])
return;
viz[x]=1;
++Ind;
lowL[x]=index[x]=Ind;
S.push(x);
in_S[x]=1;
for(size_t i=0;i<nr[x].size();++i){
if(!viz[nr[x][i]]){
DF(nr[x][i]);
lowL[x]=min(lowL[x],lowL[nr[x][i]]);
}
else{
if(in_S[x])
lowL[x]=min(lowL[x],lowL[nr[x][i]]);
}
}
if(index[x]==lowL[x]){
int nod;
++C;
do{
nod=S.top();
comp[C].push_back(nod);
S.pop();
in_S[nod]=0;
}while(nod!=x);
}
}
void afis(){
printf("%d\n",C);
for(int i=1;i<=C;++i){
for(size_t j=0; j<comp[i].size();++j)
printf("%d ",comp[i][j]);
printf("\n");
}
}
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int i,x,y;
scanf("%d%d",&N,&M);
for(i=0;i<M;++i){
scanf("%d%d",&x,&y);
nr[x].push_back(y);
}
for(i=1;i<=N;++i)
DF(i);
afis();
fclose(stdin);
fclose(stdout);
return 0;
}