Pagini recente » Cod sursa (job #512701) | Cod sursa (job #3002442) | Cod sursa (job #2744191) | Cod sursa (job #365641) | Cod sursa (job #580124)
Cod sursa(job #580124)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
#define NMAX 100050
struct muchie {
int x, y;
} S[NMAX];
int niv[NMAX], low[NMAX], N, idx, nr, n, m;
vector <int> G[NMAX], C[NMAX];
void dfs (int, int), componenta (int, int), biconex (), citire (), afisare ();
int main () {
citire ();
biconex ();
afisare ();
return 0;
}
void componenta (int nod, int fiu) {
int x, y;
nr++;
do {
x = S[N].x, y = S[N].y, N--;
C[nr].push_back (y);
} while (x != nod || y != fiu);
C[nr].push_back (x);
}
void dfs (int nod, int tata) {
int fiu;
vector <int>::iterator it;
idx++;
niv[nod] = low[nod] = idx;
for (it = G[nod].begin (); it != G[nod].end (); it++) {
fiu = *it;
if (fiu == tata) continue;
if (!niv[fiu]) {
N++, S[N].x = nod, S[N].y = fiu;
dfs (fiu, nod);
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 () {
for (int i = 1; i <= n; i++)
if (!niv[i]) dfs (i, 0);
}
void citire () {
ifstream f ("biconex.in");
int i, x, y;
f >> n >> m;
for (i = 1; i <= m; i++) {
f >> x >> y;
G[x].push_back (y);
G[y].push_back (x);
}
f.close ();
}
void afisare () {
ofstream g ("biconex.out");
g << nr << "\n";
for (int i = 1; i <= nr; i++) {
for (vector <int>::iterator it = C[i].begin (); it != C[i].end (); it++)
g << *it << " ";
g << "\n";
}
}