Pagini recente » Cod sursa (job #97820) | Cod sursa (job #2665403) | Cod sursa (job #583152) | Cod sursa (job #661057) | Cod sursa (job #597406)
Cod sursa(job #597406)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 100005
vector<int> G[MAXN], R[MAXN];
int idx, I[MAXN], ll[MAXN], use[MAXN], S[MAXN], q, rq;
void tarjan(int n){
I[n]=ll[n]=idx++;
S[++q]=n; use[n]=1;
vector<int>::iterator i;
for(i=G[n].begin(); i != G[n].end(); i++){
if(!I[*i]){
tarjan(*i);
ll[n]=min(ll[n], ll[*i]);
}
else if(use[*i])
ll[n]=min(ll[n], ll[*i]);
}
if(I[n] == ll[n]){
rq++;
do {
R[rq].push_back(S[q]);
use[S[q]]=0; q--;
} while(S[q+1] != n);
}
}
int main(){
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int N, M, i, a, b;
vector<int>::iterator ii;
scanf("%d%d", &N, &M);
for(i=1; i<=M; i++){
scanf("%d%d", &a, &b);
G[a].push_back(b);
}
idx=1; q=0; rq=0;
memset(I, 0, sizeof(I));
memset(use, 0, sizeof(use));
for(i=1; i<=N; i++)
if(!I[i])
tarjan(i);
printf("%d\n", rq);
for(i=1; i<=rq; i++){
for(ii=R[i].begin(); ii != R[i].end(); ii++)
printf("%d ", *ii);
printf("\n");
}
return 0;
}