Pagini recente » Cod sursa (job #862132) | Cod sursa (job #2656861)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <utility>
using namespace std;
vector<vector<int>> arcs;
vector<int> low, df;
vector<vector<int>> res;
stack<pair<int, int>> st;
int min(int x, int y) {
return x < y ? x : y;
}
void add_to_sol(int x, int y) {
vector<int> current_res;
int tx = 0, ty = 0;
while (tx != x || ty != y) {
tx = st.top().first;
ty = st.top().second;
st.pop();
current_res.push_back(tx);
current_res.push_back(ty);
}
res.push_back(current_res);
}
void dfs(int x, int past_x, int stackSize) {
df[x] = low[x] = stackSize;
for(int i=0; i<arcs[x].size(); ++i)
if (arcs[x][i] != past_x) {
if (df[arcs[x][i]] == 0) {
st.push(pair<int, int>(x, arcs[x][i]));
dfs(arcs[x][i], x, stackSize + 1);
low[x] = min(low[x], low[arcs[x][i]]);
if (low[arcs[x][i]] >= df[x])
add_to_sol(x, arcs[x][i]);
} else
low[x] = min(low[x], df[arcs[x][i]]);
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int n, m, x, y;
scanf("%d%d", &n, &m);
arcs.resize(n+1);
low.resize(n+1, 0);
df.resize(n+1, 0);
for(int i=0; i<m; ++i) {
scanf("%d%d", &x, &y);
arcs[x].push_back(y);
arcs[y].push_back(x);
}
for(int i=1; i<=n; ++i) {
if (! df[i])
dfs(i, 0, 1);
}
printf("%d\n", res.size());
for(int i=0; i<res.size(); ++i) {
sort(res[i].begin(), res[i].end());
for(int j=0; j<res[i].size(); ++j)
if (j == 0 || res[i][j] != res[i][j-1])
printf("%d ", res[i][j]);
printf("\n");
}
return 0;
}