Pagini recente » Cod sursa (job #2712067) | Cod sursa (job #1185491) | Cod sursa (job #3030106) | Cod sursa (job #1946101) | Cod sursa (job #478855)
Cod sursa(job #478855)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define NMAX 100050
struct {
int x, y;
} S[NMAX];
int niv[NMAX], low[NMAX], viz[NMAX], T[NMAX], n, m, nivel, N, nr_sol;
vector <int> G[NMAX];
set <int> sol[NMAX];
void citire (), biconex (), DFS (int), componenta (int, int), afisare ();
int main () {
citire ();
biconex ();
afisare ();
return 0;
}
void citire () {
freopen ("biconex.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);
G[y].push_back (x);
}
}
void componenta (int nod, int fiu) {
int x, y;
nr_sol++;
do {
x = S[N].x, y = S[N].y, N--;
sol[nr_sol].insert (x);
sol[nr_sol].insert (y);
} while (x != nod && y != fiu);
}
void DFS (int nod) {
int i, fiu;
viz[nod] = 1;
nivel++;
niv[nod] = low[nod] = nivel;
for (i = 0; i < (int) G[nod].size(); i++) {
fiu = G[nod][i];
if (fiu != T[nod])
if (!viz[fiu]) {
T[fiu] = nod;
N++, S[N].x = nod, S[N].y = fiu;
DFS (fiu);
if (low[fiu] >= niv[nod])
componenta (nod, fiu);
low[nod] = min (low[nod], low[fiu]);
}
else
low[nod] = min (low[nod], niv[fiu]);
}
}
void biconex () {
int i;
for (i = 1; i <= n; i++)
if (!viz[i])
DFS (i);
}
void afisare () {
freopen ("biconex.out", "w", stdout);
int i;
set <int>::iterator it;
printf ("%d\n", nr_sol);
for (i = 1; i <= nr_sol; i++) {
for (it = sol[i].begin(); it != sol[i].end(); it++)
printf ("%d ", *it);
printf ("\n");
}
}