Pagini recente » Cod sursa (job #2134159) | Cod sursa (job #1099589) | Cod sursa (job #1610430) | Rating Cristia-Avram Vlad (soulwise) | Cod sursa (job #477175)
Cod sursa(job #477175)
#include <cstdio>
#include <vector>
using namespace std;
#define NMAX 100050
int S[NMAX], viz[NMAX], n, m, N, sol;
vector <int> G[NMAX], GT[NMAX], CTC[NMAX];
void read ();
void DFS_1 (int);
void DFS_2 (int);
void kosaraju ();
void print ();
int main () {
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
read ();
kosaraju ();
print ();
return 0;
}
void read () {
int 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 DFS_1 (int nod) {
int i;
viz[nod] = 1;
for (i = 0; i < (int) G[nod].size(); i++)
if (!viz[ G[nod][i] ])
DFS_1 (G[nod][i]);
S[++N] = nod;
}
void DFS_2 (int nod) {
int i;
viz[nod] = 0; CTC[sol].push_back (nod);
for (i = 0; i < (int) GT[nod].size(); i++)
if (viz[ GT[nod][i] ])
DFS_2 (GT[nod][i]);
}
void kosaraju () {
int i;
for (i = 1; i <= n; i++)
if (!viz[i])
DFS_1 (i);
for ( ; N > 0; N--)
if (viz[ S[N] ]) {
sol++;
DFS_2 (S[N]);
}
}
void print () {
int i, j;
printf ("%d\n", sol);
for (i = 1; i <= sol; i++) {
for (j = 0; j < (int) CTC[i].size(); j++)
printf ("%d ", CTC[i][j]);
printf ("\n");
}
}