Pagini recente » Cod sursa (job #2349428) | Cod sursa (job #1894487) | Cod sursa (job #2706528) | Cod sursa (job #1319678) | Cod sursa (job #2756716)
#include<cstdio>
#include<vector>
using namespace std;
const int N = 100005;
int n, m, nr, nivel[N], nivelmin[N], biconex, muchiex[N], muchiey[N];
vector <int> v[N], mat[N];
bool marcat[N];
//Se dă un graf neorientat G = (V, E). Un graf se numeşte graf biconex dacă nu are puncte de articulaţie.
// Un nod se numeşte punct de articulaţie dacă subgraful obţinut prin eliminarea nodului şi a muchiilor incidente cu acesta nu mai este conex.
// O componentă biconexă a unui graf este un subgraf biconex maximal cu această proprietate.
void citire() {
scanf("%d%d", &n, &m);
int x, y;
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &x, &y);
// muchii bidirectionale (graful e neorientat )
v[x].push_back(y);
v[y].push_back(x);
}
}
void dfs(int nod) {
marcat[nod] = true;
nivelmin[nod] = nivel[nod];
// iterator : parcurge efectiv elementele
// in *it se va gasi elementul din vector ( adica vecinul )
// in loc v[nod][i] <=> *it
for (vector <int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
// daca vecinul respectiv nu a fost marcat
if (!marcat[*it]) {
// ii spun ca il pun pe urmatorul nivel
nivel[*it] = nivel[nod] + 1;
// muchiex : retine nodul la care sunt
// muchiey : retine vecinul
muchiex[++nr] = nod;
muchiey[nr] = *it;
// apelez recursiv dfs de vecin
dfs(*it);
// pornesc din radacina si tot cobor,
// daca eu cumva coborand ajung sa am un copil care are o adancime mai sus decat tatal,
// inseamna ca a fost ciclu, deci este critica
// daca nu s-a inchis un ciclu
// if spune ca este mai jos decat nodul curent => ne aflam pe o muchie critica
if (nivelmin[*it] >= nivel[nod]) {
// adaug o noua componenta biconexa
++biconex;
while (muchiex[nr] != nod || muchiey[nr] != *it)
mat[biconex].push_back(muchiey[nr--]);
mat[biconex].push_back(nod);
mat[biconex].push_back(*it);
--nr;
}
nivelmin[nod] = min(nivelmin[nod], nivelmin[*it]);
}
else
nivelmin[nod] = min(nivelmin[nod], nivel[*it]);
}
void afisare() {
printf("%d\n", biconex);
for (int i = 1; i <= biconex; ++i, printf("\n"))
for (vector <int>::iterator it = mat[i].begin(); it != mat[i].end(); ++it)
printf("%d ", *it);
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
citire();
dfs(1);
afisare();
return 0;
}