Pagini recente » Cod sursa (job #803048) | Cod sursa (job #1797918) | Cod sursa (job #2077852) | Cod sursa (job #749098) | Cod sursa (job #678940)
Cod sursa(job #678940)
#include <cstdio>
#include <vector>
using namespace std;
#define nmax 100010
vector <int> g[nmax], sol[nmax];
int n, m, cnt, u[nmax], lev[nmax], levacc[nmax], s1[nmax], s2[nmax], h, t[nmax], st[nmax];
void df(int nod)
{
u[nod]=1;
levacc[nod]=lev[nod];
int i, v;
for (i=0; i<g[nod].size(); i++)
{
v=g[nod][i];
if (t[nod]!=v)
{
if (u[v])
{
if (lev[v]<lev[nod])
{
s1[++h]=nod;
s2[h]=v;
}
levacc[nod]=min(levacc[nod], lev[v]);
} else
{
t[v]=nod;
lev[v]=lev[nod]+1;
s1[++h]=nod;
s2[h]=v;
df(v);
if (levacc[v]>=lev[nod])
{
cnt++;
if (!(s1[h]==nod && s2[h]==v))
while (!(s1[h]==nod && s2[h]==v))
{
if (st[s1[h]]!=cnt) sol[cnt].push_back(s1[h]);
st[s1[h]]=cnt;
h--;
} else
if (st[s2[h]]!=cnt)
{
sol[cnt].push_back(s2[h]);
st[s2[h]]=cnt;
}
if (st[s1[h]]!=cnt)
{
sol[cnt].push_back(s1[h]);
st[s1[h]]=cnt;
}
h--;
}
levacc[nod]=min(levacc[nod], levacc[v]);
}
}
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d", &n, &m);
int i, j, x, y;
for (i=1; i<=m; i++)
{
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
lev[1]=1;
df(1);
printf("%d\n",cnt);
for (i=1; i<=cnt; i++)
{
for (j=0; j<sol[i].size(); j++) printf("%d ",sol[i][j]);
printf("\n");
}
}