Pagini recente » Cod sursa (job #2538302) | Cod sursa (job #2244540) | Cod sursa (job #244449) | Cod sursa (job #2002253) | Cod sursa (job #1378438)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 100002;
vector<int> g[MAXN];
vector< vector<int> > sol;
stack< pair<int, int> > st;
int dfn[MAXN], low[MAXN];
int Min(int a, int b)
{
if (a < b)
return a;
return b;
}
void addSol(int x, int y)
{
vector<int> v;
int a, b;
do
{
a = st.top().first;
b = st.top().second;
v.push_back(a);
v.push_back(b);
st.pop();
} while (a != x || b != y);
sol.push_back(v);
}
void dfs(int x, int px, int level)
{
dfn[x] = low[x] = level;
for (int i = 0; i < g[x].size(); i++)
{
if (px == g[x][i])
continue;
if (dfn[g[x][i]] == 0)
{
st.push(make_pair(x, g[x][i]));
dfs(g[x][i], x, level+1);
low[x] = Min(low[x], low[g[x][i]]);
if (low[g[x][i]] >= dfn[x])
addSol(x, g[x][i]);
}
else
low[x] = min(low[x], dfn[g[x][i]]);
}
}
int main()
{
FILE *in = fopen("biconex.in", "r");
FILE *out = fopen("biconex.out", "w");
int n, m;
fscanf(in, "%d%d", &n, &m);
for (int x, y; m > 0; m--)
{
fscanf(in, "%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 0, 1);
fprintf(out, "%d\n", sol.size());
for (int i = 0; i < sol.size(); i++)
{
sort(sol[i].begin(), sol[i].end());
sol[i].erase(unique(sol[i].begin(), sol[i].end()), sol[i].end());
for (int j = 0; j < sol[i].size(); j++)
fprintf(out, "%d ", sol[i][j]);
fprintf(out, "\n");
}
return 0;
}