Pagini recente » Cod sursa (job #2876220) | Cod sursa (job #25047) | Cod sursa (job #2446617) | Cod sursa (job #1876606) | Cod sursa (job #1667767)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 100009;
vector < int > all[nmax] , g[nmax];
pair < int , int > is[nmax];
int lvl[nmax] , lmin[nmax] , mark[nmax];
int n , m , i , a , b , j , S , top;
void runBC(pair < int , int > edge)
{
vector < int > bc;
while (true)
{
pair < int , int > act = is[top--];
bc.push_back(act.second);
if (act == edge)
{
bc.push_back(act.first);
break;
}
}
all[++S] = bc;
}
void dfs(int act , int up)
{
lvl[act] = lvl[up] + 1;
lmin[act] = lvl[act];
mark[act] = 1;
for (int i = 0 ; i < g[act].size() ; ++i)
{
int x = g[act][i];
if (x == up) continue;
if (!mark[x])
{
is[++top] = make_pair(act , x);
dfs(x , act);
lmin[act] = min(lmin[act] , lmin[x]);
if (lvl[act] <= lmin[x]) runBC({act , x});
}
else lmin[act] = min(lmin[act] , lvl[x]);
}
}
int main()
{
freopen("biconex.in" , "r" , stdin);
freopen("biconex.out" , "w" , stdout);
scanf("%d" , &n);
scanf("%d" , &m);
for (i = 1 ; i <= m ; ++i)
{
scanf("%d" , &a);
scanf("%d" , &b);
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1 , 0);
printf("%d\n" , S);
for (i = 1 ; i <= S ; ++i , printf("\n"))
for (j = 0 ; j < all[i].size() ; ++j)
printf("%d " , all[i][j]);
return 0;
}