Pagini recente » Cod sursa (job #1859763) | Cod sursa (job #2547647) | Cod sursa (job #2736777) | Cod sursa (job #1395704) | Cod sursa (job #2725357)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 100000;
struct muchie {
int dad, nod;
muchie(int _dad = 0, int _nod = 0) : dad(_dad), nod(_nod) {}
};
int n, m;
int niv[NMAX + 5], highest[NMAX + 5];
vector<int> v[NMAX + 5];
vector<muchie> stiva;
vector<vector<int>> cbc;
void pop_cbc(int nod, int dad) {
vector<int> new_cbc, aux;
muchie crt;
do {
crt = stiva.back();
stiva.pop_back();
new_cbc.push_back(crt.dad);
new_cbc.push_back(crt.nod);
} while(crt.dad != dad || crt.nod != nod);
sort(new_cbc.begin(), new_cbc.end());
for(int i = 0; i < new_cbc.size(); i++)
if(i == 0 || new_cbc[i] != new_cbc[i - 1])
aux.push_back(new_cbc[i]);
cbc.push_back(aux);
}
void dfs(int nod, int dad) {
highest[nod] = niv[nod] = niv[dad] + 1;
for(int vec: v[nod]) {
if(vec == dad)
continue;
if(niv[vec] != 0)
highest[nod] = min(highest[nod], niv[vec]);
else {
stiva.push_back(muchie(nod, vec));
dfs(vec, nod);
highest[nod] = min(highest[nod], highest[vec]);
if(highest[vec] >= niv[nod])
pop_cbc(vec, nod);
}
}
}
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 <= m; i++) {
scanf("%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
printf("%d\n", cbc.size());
for(vector<int> crt_cbc: cbc) {
for(int crt: crt_cbc)
printf("%d ", crt);
printf("\n");
}
return 0;
}