Pagini recente » Cod sursa (job #1448008) | Cod sursa (job #375353) | Cod sursa (job #1999956) | Cod sursa (job #337090) | Cod sursa (job #771652)
Cod sursa(job #771652)
/*
Componentele biconexe dintr-un graf.
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <stdio.h>
#define MAXN 100001
#define min(a, b) (a < b ? a : b)
using namespace std;
int nr_noduri, nr_muchii;
vector <int> graf[MAXN], nivel, low;
vector <vector <int> > comp_biconexe;
stack <pair <int, int> > stiva;
void componenta (int u, int v) {
vector <int> comp;
int u1, v1;
do {
u1 = stiva.top().first;
comp.push_back(u1);
v1 = stiva.top().second;
comp.push_back(v1);
stiva.pop();
} while (u1 != u || v1 != v);
comp_biconexe.push_back(comp);
}
void dfs (int u, int t, int idx) {
nivel[u] = low[u] = idx;
for (int v = 0; v < graf[u].size(); v++) {
if (graf[u][v] == t)
continue;
if (nivel[graf[u][v]] < 0) {
stiva.push(make_pair(u, graf[u][v]));
dfs(graf[u][v], u, idx++);
low[u] = min(low[u], low[graf[u][v]]);
if (low[graf[u][v]] >= nivel[u])
componenta(u, graf[u][v]);
}
else
low[u] = min(low[u], nivel[graf[u][v]]);
}
}
int main () {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int i, j, x, y;
scanf("%d %d", &nr_noduri, &nr_muchii);
for (i = 0; i < nr_muchii; i++) {
scanf("%d %d", &x, &y);
graf[x].push_back(y);
graf[y].push_back(x);
}
nivel.resize(nr_noduri + 1);
nivel.assign(nr_noduri + 1, -1);
low.resize(nr_noduri + 1);
dfs(1, 0, 0);
printf("%d\n", comp_biconexe.size());
for (i = 0; i < comp_biconexe.size(); i++) {
sort(comp_biconexe[i].begin(), comp_biconexe[i].end());
comp_biconexe[i].erase(unique(comp_biconexe[i].begin(), comp_biconexe[i].end()), comp_biconexe[i].end());
for (j = 0; j < comp_biconexe[i].size(); j++)
printf("%d ", comp_biconexe[i][j]);
printf("\n");
}
return 0;
}