Pagini recente » Cod sursa (job #3192027) | Cod sursa (job #2691994) | Cod sursa (job #1563915) | Cod sursa (job #2396894) | Cod sursa (job #374861)
Cod sursa(job #374861)
// Kosaraju
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define Nmax 100010
int n, m, i, x, y, nr, N, j;
int S[Nmax];
char viz[Nmax];
vector <int> G[Nmax], T[Nmax], CTC[Nmax];
void citire () {
FILE *f = fopen ("ctc.in", "r");
fscanf (f, "%d %d", &n, &m);
for (i = 1; i <= m; i++) {
fscanf (f, "%d %d", &x, &y);
G[x].push_back (y);
T[y].push_back (x);
}
fclose (f);
}
void DFS1 (int nod) {
int i; viz[nod] = 1;
for (i = 0; i < (int)G[nod].size(); i++)
if (!viz[G[nod][i]]) DFS1 (G[nod][i]);
S[++N] = nod;
}
void DFS2 (int nod) {
viz[nod] = 0; CTC[nr].push_back (nod);
int i;
for (i = 0; i < (int)T[nod].size(); i++)
if (viz[T[nod][i]]) DFS2 (T[nod][i]);
}
void kosaraju () {
for (i = 1; i <= n; i++)
if (!viz[i])
DFS1 (i);
for (; N; N--)
if (viz[S[N]])
nr++, DFS2 (S[N]);
}
void afisare () {
FILE *g = fopen ("ctc.out", "w");
fprintf (g, "%d\n", nr);
for (i = 1; i <= nr; i++) {
for (j = 0; j < (int)CTC[i].size(); j++)
fprintf (g, "%d ", CTC[i][j]);
fprintf (g, "\n");
}
fclose (g);
}
int main () {
citire ();
kosaraju ();
afisare ();
return 0;
}