Pagini recente » Cod sursa (job #1179990) | Istoria paginii runda/ceva_ez_v2/clasament | Cod sursa (job #2965852) | Cod sursa (job #365038) | Cod sursa (job #877554)
Cod sursa(job #877554)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <stack>
#include <vector>
using namespace std;
const int MAXN = 100001;
int n, m;
int dfn[MAXN];
int low[MAXN];
vector<int> G[MAXN];
vector<set<int> > sols;
stack<pair<int, int> > st;
void recover(int x, int y)
{
set<int> sol;
int tx, ty;
do {
tx = st.top().first;
ty = st.top().second;
st.pop();
sol.insert(tx);
sol.insert(ty);
} while (x != tx && y != ty);
sols.push_back(sol);
}
void dfs(int prev, int node, int num)
{
low[node] = dfn[node] = num;
for (int i = 0; i < G[node].size(); ++i) {
int next = G[node][i];
if (prev == next)
continue;
if (dfn[next] == -1) {
st.push(make_pair(node, next));
dfs(node, next, num + 1);
low[node] = min(low[node], low[next]);
if (low[next] >= dfn[node])
recover(node, next);
} else {
low[node] = min(low[node], low[next]);
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 0; i < m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
memset(dfn, -1, sizeof(dfn));
for (int i = 1; i <= n; ++i)
if (dfn[i] == -1)
dfs(0, i, 0);
printf("%lu\n", sols.size());
for (int i = 0; i < sols.size(); ++i) {
set<int>::iterator it;
for (it = sols[i].begin(); it != sols[i].end(); ++it)
printf("%d ", *it);
printf("\n");
}
return 0;
}