Pagini recente » Cod sursa (job #556671) | Cod sursa (job #221085) | Cod sursa (job #1287624) | Cod sursa (job #2280705) | Cod sursa (job #454051)
Cod sursa(job #454051)
#include <stdio.h>
#include <set>
#include <vector>
#include <utility>
using namespace std;
#define maxN 100100
#define maxM 200100
#define oo 100100
#define ROOT 1
int N, M, Nr, cate_ramase;
int low[maxN], nivel[maxN];
int Biconexa[maxM];
vector <int> G[maxN], Ind[maxN], ind;
vector < pair <int, int> > stack;
set <int> Sol_vec[maxN];
char art_point[maxN], viz[maxN];
void baga_marfa () {
Sol_vec[Nr].insert(stack.back().first); // adaug cele 2 noduri la biconexa, in caz ca mai sunt deja nu apar de 2 ori
Sol_vec[Nr].insert(stack.back().second);
Biconexa[ind.back()] = Nr; // tin minte din ce biconexa face parte muchia
stack.pop_back(); // scot ultima muchie din stiva
ind.pop_back();
}
void df (int nod, int parinte) {
int niv_min = oo; // nivelul minim la care pot ajunge din descendenti + muchie de intoarcere
viz[nod] = 1; // marchez nodul ca vizitat
nivel[nod] = nivel[parinte] + 1; // nivelul nodului este nivelul parintelui + 1
cate_ramase --; // am mai vizitat un nod, scad numarul celor nevizitate
low[nod] = nivel[nod]; // momentan nivelul minim la care se poate ajunge din nodul curent in sus este nivelul lui
for (vector <int> :: iterator it = G[nod].begin(); it != G[nod].end(); ++ it) { // parcurg vecinii
if (*it == parinte || (viz[*it] && nivel[*it] > nivel[nod])) continue; // in caz ca e parintele ma opresc
stack.push_back(make_pair(nod, *it)); // bag muchia curenta in stiva
ind.push_back(Ind[nod][it - G[nod].begin()]); // si indicele ei, o sa ma ajute mai tarziu la reconstructie
if (viz[*it]) { // daca a mai fost vizitat, e muchie de intoarcere
low[nod] = min(low[nod], nivel[*it]); // vad daca pot ajunge mai sus decat pana acum
} else {
df(*it, nod); // ma duc pe muchia de dus
niv_min = min(niv_min, low[*it]); // modific corespunzator nivelul minim la care se poate ajunge din fii
if (low[*it] >= nivel[nod] && nod != ROOT) { // daca toti descendentii lui ajung maxim pana la nivelul lui
art_point[nod] = 1; // e punct de articulatie
++ Nr; // apare o noua biconexa
for (; stack.back() != make_pair(nod, *it); baga_marfa());
baga_marfa(); // scot din stiva pana ajung la muchia curenta, inclusiv ea.
}
}
if (nod == ROOT && cate_ramase) { // ma uit daca nu e nodul 1 punct de articulatie
art_point[nod] = 1;
++ Nr;
for (; stack.back() != make_pair(nod, *it); baga_marfa()); // adaug biconexa
baga_marfa();
}
}
low[nod] = min(low[nod], niv_min); // marchez nivelul minim la care poate ajunge
}
int main () {
int i, a, b;
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &N, &M); // citesc numarul de noduri si numarul de muchii
for (i = 1; i <= M; ++ i) {
scanf("%d%d", &a, &b); // citesc muchiile
G[a].push_back(b); // construiesc graful
G[b].push_back(a);
Ind[a].push_back(i); // tin minte indicii muchiilor
Ind[b].push_back(i);
}
cate_ramase = N; // cate noduri nu au fost vizitate
df(ROOT, 0); // parcurg in adancime
if (stack.size()) {
++ Nr;
for (; stack.size(); baga_marfa());
}
printf("%d\n", Nr);
for (i = 1; i <= Nr; ++ i) {
for (set <int> :: iterator it = Sol_vec[i].begin(); it != Sol_vec[i].end(); ++ it)
printf("%d ", *it);
puts("");
}
}