Pagini recente » Cod sursa (job #2950861) | Cod sursa (job #422747) | Cod sursa (job #2563491) | Cod sursa (job #2259585) | Cod sursa (job #2574069)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 100000
using namespace std;
struct muchie {
int t, f;
muchie(int tt = 0, int ff = 0) {
t = tt;
f = ff;
}
};
int n, m, ncomp, num, start;
int dfn[NMAX + 5], low[NMAX + 5];
vector<muchie> st;
vector<int> v[NMAX + 5], cbc[NMAX + 5];
void comp_biconexa(int u, int x) {
muchie crt;
ncomp++;
do {
crt = st.back();
st.pop_back();
cbc[ncomp].push_back(crt.t);
cbc[ncomp].push_back(crt.f);
} while(crt.t != u || crt.f != x);
sort(cbc[ncomp].begin(), cbc[ncomp].end());
}
void biconex(int u, int tu) {
dfn[u] = low[u] = ++num;
for(int x: v[u]) {
if(x == tu)
continue;
if(dfn[x] < dfn[u])
st.push_back(muchie(u, x));
if(dfn[x] == -1) { /// nu e muchie de intoarcere
biconex(x, u);
low[u] = min(low[u], low[x]);
if(low[x] >= dfn[u]) /// u e pct de articulatie
comp_biconexa(u, x);
}
else
low[u] = min(low[u], dfn[x]);
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int x, y;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
dfn[i] = low[i] = -1;
for(int i = 1; i <= m; i++) {
scanf("%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
ncomp = num = 0;
start = 1;
st.push_back(muchie(-1, 1));
biconex(1, -1);
printf("%d\n", ncomp);
for(int i = 1; i <= ncomp; i++) {
for(int j = 0; j < cbc[i].size(); j++)
if(j == 0 || cbc[i][j] != cbc[i][j - 1])
printf("%d ", cbc[i][j]);
printf("\n");
}
return 0;
}