Pagini recente » DeehoroEjkoli | Cod sursa (job #2956572) | Cod sursa (job #750244) | Cod sursa (job #2382574) | Cod sursa (job #1283239)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
vector<int> g[100001];
vector< vector<int> > sol;
stack< pair<int, int> > st;
int dfn[100001], low[100001];
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 (g[x][i] == px)
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());
fprintf(out, "%d", sol[i][0]);
for (int j = 1; j < sol[i].size(); ++j)
fprintf(out, " %d", sol[i][j]);
fprintf(out, "\n");
}
return 0;
}