Pagini recente » Cod sursa (job #369928) | Cod sursa (job #2503882) | Cod sursa (job #108634) | Cod sursa (job #2980421) | Cod sursa (job #2192879)
#include<stdio.h>
#include<vector>
#define Nmax 100010
using namespace std;
int n, m , viz[Nmax], i , a , b , ctc, S[Nmax], nn, N, j;
vector<int> G[Nmax], T[Nmax], Ctc[Nmax];
void sortaret(int nod) {
int i, N = G[nod].size();
viz[nod] = 1;
for (i = 0; i < N; i++) {
if (!viz[G[nod][i]]) sortaret(G[nod][i]);
}
S[--nn] = nod ;
}
void dfs(int nod) {
int i, N = T[nod].size();
Ctc[ctc].push_back(nod);
viz[nod] = 0;
for (i = 0; i < N; i++) {
if (viz[T[nod][i]]) dfs(T[nod][i]);
}
}
int main() {
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for (i = 1; i <= m; i++) {
scanf("%d %d", &a, &b);
G[a].push_back(b);
T[b].push_back(a);
}
nn = n + 1 ;
for (i = 1; i <= n; i++) {
if(!viz[i]) sortaret(i);
}
for (i = 1; i <= n; i++) {
if (viz[S[i]]) ctc++, dfs(S[i]);
}
printf("%d\n", ctc);
for (i = 1; i <= ctc; i++) {
N = Ctc[i].size();
for (j = 0; j < N; j++) {
printf("%d ", Ctc[i][j]);
}
printf("\n");
}
return 0 ;
}