Pagini recente » Cod sursa (job #2229476) | Cod sursa (job #2089886) | Cod sursa (job #1696902) | Cod sursa (job #776529) | Cod sursa (job #771722)
Cod sursa(job #771722)
/*
Componentele biconexe dintr-un graf.
*/
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#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;
while (u1 != u || v1 != v) {
u1 = stiva.top().first;
comp.push_back(u1);
v1 = stiva.top().second;
comp.push_back(v1);
stiva.pop();
}
comp_biconexe.push_back(comp);
}
void dfs (int u, int t, int idx) {
nivel[u] = low[u] = idx;
for (int v = 0; v < (int)graf[u].size(); v++) {
int n = graf[u][v];
if (n == t)
continue;
if (nivel[n] < 0) {
stiva.push(make_pair(u, n));
dfs(n, u, idx + 1);
low[u] = min(low[u], low[n]);
if (low[graf[u][v]] >= nivel[u])
componenta(u, n);
}
else
low[u] = min(low[u], nivel[n]);
}
}
int main(void) {
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 < (int)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 < (int)comp_biconexe[i].size(); ++ j)
printf("%d ", comp_biconexe[i][j]);
printf("\n");
}
return 0;
}