Pagini recente » Cod sursa (job #1739956) | Cod sursa (job #610925) | Cod sursa (job #1950138) | Cod sursa (job #1216768) | Cod sursa (job #383841)
Cod sursa(job #383841)
#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
#define MAX_N 100010
int n, m, p, q, k;
int timp[MAX_N], fol[MAX_N], stiv[MAX_N];
vector <int> G[MAX_N], A[MAX_N], sol[MAX_N];
void dfs(int nod) {
fol[nod] = 1;
int len = G[nod].size();
for (int i = 0; i < len; i++)
if (!fol[G[nod][i]])
dfs(G[nod][i]);
stiv[++stiv[0]] = nod;
}
void tare_conex(int nod) {
sol[k].push_back(nod);
fol[nod] = 1;
int len = A[nod].size();
for (int i = 0; i < len; i++)
if (!fol[A[nod][i]])
tare_conex(A[nod][i]);
}
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &p, &q);
G[p].push_back(q);
A[q].push_back(p);
}
//pasul I : fac df-urile initiale (gen sortare topologica)
for (int i = 1; i <= n; i++)
if (!fol[i])
dfs(i);
memset(fol, 0, sizeof(fol));
k = 0;
for (int i = n; i >= 1; i--)
if (!fol[stiv[i]]) {
k++;
tare_conex(stiv[i]);
}
printf("%d\n", k);
for (; k; k--) {
int len = sol[k].size();
for (int i = 0; i < len; i++)
printf("%d ", sol[k][i]);
printf("\n");
}
return 0;
}