Pagini recente » Cod sursa (job #2388837) | Cod sursa (job #2438644) | Cod sursa (job #1935739) | Cod sursa (job #1336326) | Cod sursa (job #3200453)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int NMAX = 1e5;
vector<int> G[NMAX + 1];
int low[NMAX + 1], niv[NMAX + 1];
stack<pair<int, int>> st;
set<int> cb[NMAX + 1];
int cnt;
void dfs(int node, int dad) {
niv[node] = niv[dad] + 1;
low[node] = niv[node];
for(auto next : G[node]) {
if(next == dad) {
continue;
}
if(niv[next]) {
low[node] = min(low[node], niv[next]);
} else {
st.push({node, next});
dfs(next, node);
low[node] = min(low[node], low[next]);
if(low[next] >= niv[node]) {
cnt++;
while(true) {
auto it = st.top();
st.pop();
cb[cnt].insert(it.first);
cb[cnt].insert(it.second);
if(it.first == node && it.second == next) {
break;
}
}
}
}
}
}
int main() {
int n, m;
f >> n >> m;
while(m--) {
int x, y;
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1, 0);
g << cnt << '\n';
for(int i = 1; i <= cnt; i++) {
for(auto it : cb[i]) {
g << it << ' ';
}
g << '\n';
}
return 0;
}