Pagini recente » Cod sursa (job #260993) | Cod sursa (job #1599910) | Cod sursa (job #2621777) | Cod sursa (job #886358) | Cod sursa (job #300201)
Cod sursa(job #300201)
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
#define N 100005
vector < int > v[N];
vector < int > w[N];
bool ins[N];
stack < int > s;
int n,ind[N],sub[N],indice,nrm;
int minim(int x,int y){
return x<y?x:y;
}
void dfs(int x){
ind[x] = ++indice;
s.push(x);
ins[x] = true;
sub[x] = indice;
int nr = v[x].size(),y;
for(int i=0 ; i<nr ; ++i){
y=v[x][i];
if(ind[y] == 0 || ins[y]){
if(ind[y] == 0)
dfs(y);
sub[x] = minim(sub[x],sub[y]);
}
}
if(sub[x] == ind[x]){
++nrm;
do{
y=s.top();
s.pop();
w[nrm].push_back(y);
ins[y] = false;
}while(y != x);
}
}
void solve(){
int nr;
for(int i=1 ; i<=n ; ++i)
if(ind[i] == 0)
dfs(i);
printf("%d\n",nrm);
for(int i=1 ; i<=nrm ; ++i){
nr = w[i].size();
for(int j=0 ; j<nr ; ++j)
printf("%d ",w[i][j]);
printf("\n");
}
}
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int m,x,y;
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i){
scanf("%d%d",&x,&y);
v[x].push_back(y);
}
solve();
return 0;
}