Pagini recente » Cod sursa (job #725841) | Cod sursa (job #1177280) | Cod sursa (job #3251123) | Cod sursa (job #2887124) | Cod sursa (job #2174405)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100000;
struct muchie
{
int x, y;
}; stack <muchie> st; muchie aux;
vector <int> g[NMAX + 5], sol[NMAX + 5];
int t[NMAX + 5], niv[NMAX + 5], low[NMAX + 5], nivel, nr;
void solve(int a, int b)
{
int x, y; ++nr;
do {
x = st.top().x ; y = st.top().y;
st.pop(); sol[nr].push_back(y);
} while (x != a && y != b);
sol[nr].push_back(x);
}
void dfs(int x)
{
int y; ++nivel;
niv[x] = low[x] = nivel;
for (int i = 0; i < g[x].size(); ++i)
{
y = g[x][i];
if (y != t[x])
if (niv[y] == 0)
{
aux.x = x; aux.y = y; st.push(aux);
t[y] = x; dfs(y);
if (low[y] >= niv[x])
solve(x, y);
low[x] = min(low[x], low[y]);
}
else
low[x] = min(low[x], niv[y]);
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int n, m, x, y;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i)
{
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; ++i)
if (niv[i] == 0)
dfs(i);
printf("%d\n", nr);
for (int i = 1; i <= nr; ++i)
{
for (int j = 0; j < sol[i].size(); ++j)
printf("%d ", sol[i][j]);
printf("\n");
}
return 0;
}