Pagini recente » Cod sursa (job #514494) | Cod sursa (job #3218694) | Cod sursa (job #2888715) | Cod sursa (job #1402240) | Cod sursa (job #2367119)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
vector< int > gr[MAXN];
stack< pair< int, int > > edges;
vector< int > sol[MAXN];
int cntbico = 0;
int level[MAXN];
int minim[MAXN];
void dfs(int node, int d) {
level[node] = minim[node] = d;
for(auto &x : gr[node]) {
if(!level[x]) {
edges.push({node, x});
dfs(x, d + 1);
if(minim[x] >= level[node]) {
++cntbico;
int a, b;
do {
tie(a, b) = edges.top();
sol[cntbico].emplace_back(a);
sol[cntbico].emplace_back(b);
edges.pop();
} while(a != node || b != x);
sort(sol[cntbico].begin(), sol[cntbico].end());
sol[cntbico].erase(unique(sol[cntbico].begin(), sol[cntbico].end()), sol[cntbico].end());
}
minim[node] = min(minim[node], minim[x]);
} else minim[node] = min(minim[node], level[x]);
}
}
int main () {
#ifdef HOME
freopen("input", "r", stdin);
#define f cin
#define g cout
#else
ifstream f("biconex.in");
ofstream g("biconex.out");
#endif // HOME
int n, m;
f >> n >> m;
for(int i = 0; i < m; ++i) {
int a, b;
f >> a >> b;
gr[a].emplace_back(b);
gr[b].emplace_back(a);
}
dfs(1, 1);
g << cntbico << '\n';
for(int i = 1; i <= cntbico; ++i) {
for(auto &x : sol[i]) g << x << ' ';
g << '\n';
}
return 0;
}