Pagini recente » Cod sursa (job #1726188) | Cod sursa (job #824969) | Cod sursa (job #970135) | Istoria paginii utilizator/roxanaionita | Cod sursa (job #1645972)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX=100000;
int n,m;
struct muchie
{
int x,y;
}S[NMAX];
vector <int> G[NMAX+2],sol[NMAX+2];
bool artic_vertex[NMAX+2];
int low[NMAX+2], disc[NMAX+2], dad[NMAX+2];
int tim,k,nr;
void articPoint(int u)
{
int v;
++tim;
disc[u]=low[u]=tim;
for(int j=0; j<(int)G[u].size(); j++)
{
v=G[u][j];
if(!disc[v])
{
k++;
S[k].x=u;
S[k].y=v;
dad[v]=u;
articPoint(v);
if(low[v] >= disc[u])
{
nr++;
int a,b;
do{
a=S[k].x;
b=S[k].y;
k--;
sol[nr].push_back(b);
}while(a!=u && b!=v);
sol[nr].push_back(u);
}
low[u]=min(low[u], low[v]);
}
else
if (v != dad[u])
low[u]=min(low[u],low[v]);
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i=1; i<=m; i++)
{
int u,v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i=1; i<=n; i++)
dad[i]=-1;
for(int i=1; i<=n; i++)
if(!disc[i])
articPoint(i);
printf("%d\n", nr);
for(int i=1; i<=nr; i++)
{
for(int j=0; j<(int)sol[i].size(); j++)
printf("%d ", sol[i][j]);
printf("\n");
}
return 0;
}