Pagini recente » Cod sursa (job #1178430) | Cod sursa (job #2895930) | Cod sursa (job #752707) | Cod sursa (job #735640) | Cod sursa (job #651325)
Cod sursa(job #651325)
#include <cstdio>
#include <vector>
using namespace std;
#define NMAX 100050
bool IN_S[NMAX];
int S[NMAX], niv[NMAX], low[NMAX], N, nr, n, m;
vector <int> CTC[NMAX], G[NMAX];
void tarjan (), dfs (int, int), input (), output ();
int main () {
input ();
tarjan ();
output ();
return 0;
}
void tarjan () {
for (int i = 1; i <= n; i++)
if (!niv[i])
dfs (0, i);
}
void dfs (int tata, int nod) {
int fiu, aux;
vector <int>::iterator it;
low[nod] = niv[nod] = niv[tata] + 1; S[++N] = nod, IN_S[nod] = 1;
for (it = G[nod].begin (); it != G[nod].end (); it++) {
fiu = *it;
if (!niv[fiu]) {
dfs (nod, fiu);
low[nod] = min (low[nod], low[fiu]);
}
else if (IN_S[fiu])
low[nod] = min (low[nod], low[fiu]);
}
if (niv[nod] == low[nod]) {
nr++;
do {
aux = S[N--]; IN_S[aux] = 0;
CTC[nr].push_back (aux);
} while (aux != nod);
}
}
void input () {
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 output () {
freopen ("ctc.out", "w", stdout);
vector <int>::iterator it;
printf ("%d\n", nr);
for (int i = 1; i <= nr; i++) {
for (it = CTC[i].begin (); it != CTC[i].end (); it++)
printf ("%d ", *it);
printf ("\n");
}
}