Pagini recente » Cod sursa (job #298205) | Cod sursa (job #1127158) | Cod sursa (job #1878734) | Cod sursa (job #2301403) | Cod sursa (job #477409)
Cod sursa(job #477409)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 100050
int S[NMAX], S_viz[NMAX], idx[NMAX], low[NMAX], n, m, nr_ctc, index, N;
vector <int> G[NMAX], CTC[NMAX];
void citire ();
void ctc ();
void tarjan (int);
void afisare ();
int main () {
citire ();
ctc ();
afisare ();
return 0;
}
void citire () {
freopen ("ctc.in", "r", stdin);
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);
}
}
void ctc () {
int i;
for (i = 1; i <= n; i++)
if (!idx[i])
tarjan (i);
}
void tarjan (int nod) {
int i, fiu, aux;
index++;
idx[nod] = index, low[nod] = index;
S[++N] = nod, S_viz[nod] = 1;
for (i = 0; i < (int) G[nod].size(); i++) {
fiu = G[nod][i];
if (!idx[fiu]) {
tarjan (fiu);
low[nod] = min (low[nod], low[fiu]);
}
else if (S_viz[fiu])
low[nod] = min (low[nod], low[fiu]);
}
if (idx[nod] == low[nod]) {
nr_ctc++;
do {
aux = S[N--], S_viz[aux] = 0;
CTC[nr_ctc].push_back (aux);
} while (aux != nod);
}
}
void afisare () {
freopen ("ctc.out", "w", stdout);
int i, j;
printf ("%d\n", nr_ctc);
for (i = 1; i <= nr_ctc; i++) {
for (j = 0; j < (int) CTC[i].size(); j++)
printf ("%d ", CTC[i][j]);
printf ("\n");
}
}