Pagini recente » Cod sursa (job #2243473) | Cod sursa (job #1361515) | Cod sursa (job #292523) | Cod sursa (job #149405) | Cod sursa (job #554877)
Cod sursa(job #554877)
#include <cstdio>
#include <list>
using namespace std;
#define NMAX 100050
int S[NMAX], viz[NMAX], N, sol, n;
list <int> G[NMAX], GT[NMAX], CTC[NMAX];
void citire (), kosaraju (), afisare (), DFS1 (int), DFS2 (int);
int main () {
citire ();
kosaraju ();
afisare ();
return 0;
}
void citire () {
freopen ("ctc.in", "r", stdin);
int m, i, x, y;
scanf ("%d %d", &n, &m);
for (i = 1; i <= m; i++) {
scanf ("%d %d", &x, &y);
G[x].push_back (y);
GT[y].push_back (x);
}
}
void DFS1 (int nod) {
S[++N] = nod, viz[nod] = 1;
for (list <int>::iterator it = G[nod].begin (); it != G[nod].end (); it++)
if (!viz[*it])
DFS1 (*it);
}
void DFS2 (int nod) {
viz[nod] = 0; CTC[sol].push_back (nod);
for (list <int>::iterator it = GT[nod].begin (); it != GT[nod].end (); it++)
if (viz[*it])
DFS2 (*it);
}
void kosaraju () {
for (int i = 1; i <= n; i++)
if (!viz[i])
DFS1 (i);
for ( ; N > 0; N--) {
if (viz[ S[N] ]) {
sol++;
DFS2 (S[N]);
}
}
}
void afisare () {
freopen ("ctc.out", "w", stdout);
printf ("%d\n", sol);
for (int i = 1; i <= sol; i++) {
for (list <int>::iterator it = CTC[i].begin (); it != CTC[i].end (); it++)
printf ("%d ", *it);
printf ("\n");
}
}