Pagini recente » Cod sursa (job #584656) | Cod sursa (job #903518) | Cod sursa (job #2736640) | Cod sursa (job #2176470) | Cod sursa (job #2065101)
# include <bits/stdc++.h>
using namespace std;
const int nmax = 2 * 1e5 + 5;
vector <int> ans[nmax], G[nmax];
stack < pair <int, int> > st;
bool selected[nmax];
int low[nmax], lvl[nmax], n, m, i, N;
void biconex(pair <int, int> x)
{
++N;
while (!st.empty())
{
pair <int, int> y = st.top();
ans[N].push_back(y.second);
st.pop();
if (y == x) break;
}
ans[N].push_back(x.first);
}
void dfs(int node)
{
selected[node] = true;
low[node] = lvl[node];
for (auto &it: G[node])
if (!selected[it])
{
lvl[it] = lvl[node] + 1;
st.push({node, it});
dfs(it);
if (lvl[node] <= low[it]) biconex({node, it});
low[node] = min(low[node], low[it]);
}
else low[node] = min(low[node], lvl[it]);
}
int main ()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d\n", &n, &m);
for (int i = 1; i <= m; ++i)
{
int x, y;
scanf("%d %d\n", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
printf("%d\n", N);
for (i = 1; i <= N; ++i)
{
for (auto &it: ans[i])
printf("%d ", it);
printf("\n");
}
return 0;
}