Pagini recente » Cod sursa (job #2627470) | Cod sursa (job #1324173) | Cod sursa (job #100316) | Cod sursa (job #611336) | Cod sursa (job #1690010)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 10;
int n , m , i , nrc;
bool used[nmax];
int low[nmax] , lvl[nmax];
vector < int > g[nmax] , ans[nmax];
stack < pair < int , int > > s;
void runBC(pair < int , int > edge)
{
nrc++;
while (true)
{
pair < int , int > act = s.top();
s.pop();
ans[nrc].push_back(act.second);
if (act == edge) break;
}
ans[nrc].push_back(edge.first);
}
void dfs(int node)
{
used[node] = 1;
low[node] = lvl[node];
for (auto &it : g[node])
{
if (used[it])
{
low[node] = min(low[node] , lvl[it]);
continue;
}
lvl[it] = lvl[node] + 1;
s.push({node,it});
dfs(it);
low[node] = min(low[node] , low[it]);
if (lvl[node] <= low[it]) runBC({node,it});
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d", &n, &m);
for (i = 1; i <= m; ++i)
{
int x , y;
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
lvl[1] = 1; dfs(1);
printf("%d\n", nrc);
for (i = 1; i <= nrc; ++i, printf("\n"))
for (auto &it : ans[i])
printf("%d ", it);
return 0;
}