Pagini recente » Cod sursa (job #3171525) | Cod sursa (job #1392780) | Cod sursa (job #228398) | Cod sursa (job #518517) | Cod sursa (job #434174)
Cod sursa(job #434174)
#include <stdio.h>
#include <algorithm>
#define IN "biconex.in"
#define OUT "biconex.out"
#define L 100005
using namespace std;
struct nod
{
int inf;
nod *next;
}*V[L],*R[L];
int num, n, m, sf, a, b, nr;
int niv[L];
int viz[L];
int low[L];
int st[L*2];
void add(nod *&A,int i)
{
nod *q=new nod;
q->inf=i;
q->next=A;
A=q;
}
void citire()
{
scanf ("%d %d", &n, &m);
for (int i=0;i<m;i++)
{
scanf ("%d %d", &a, &b);
add(V[a],b);
add(V[b],a);
}
}
void ad(int a,int b)
{
do
{
add(R[num], st[--sf]);
add(R[num], st[--sf]);
}while (st[sf]!=a || st[sf+1]!=b);
num++;
}
void df(int P)
{
viz[P]=1;
low[P]=niv[P]=nr++;
for (nod *i=V[P];i;i=i->next)
if (!viz[i->inf])
{
st[sf++]=i->inf;
st[sf++]=P;
df(i->inf);
if (low[i->inf]>=niv[P])
ad(i->inf, P);
low[P]= min(low[P],low[i->inf]);
}
else
low[P]=min(low[P], niv[i->inf]);
}
void solve()
{
for (int i=1;i<=n;i++)
if (!viz[i])
df(i);
printf("%d\n",num);
for (int i=0;i<num;i++)
{
for (nod *j=R[i];j;j=j->next)
viz[j->inf]=0;
for (nod *j=R[i];j;j=j->next)
if (!viz[j->inf])
{
viz[j->inf]=1;
printf("%d ", j->inf);
}
printf("\n");
}
}
int main()
{
freopen (IN ,"r", stdin);
freopen (OUT , "w", stdout);
citire();
solve();
return 0;
}