Pagini recente » Cod sursa (job #2081119) | Cod sursa (job #354465) | Cod sursa (job #1533631) | Cod sursa (job #320168) | Cod sursa (job #720504)
Cod sursa(job #720504)
#include<stdio.h>
#include<vector>
#include<stack>
#define infile "biconex.in"
#define outfile "biconex.out"
#define nmax 100002
using namespace std;
int n,m,k,hh; //nr noduri/muchii
int xx[200002],pp[200002];
int timp,start,nrfii,nrc,x1,x2,p1,p2;
int nrv[nmax];//numar vecini
int sus[nmax]; // cel mai de sus nod in care poate urca
int d[nmax];//nodul a fost atins la pasul k
struct pereche
{
int x,y;
};
pereche s[200002],w[200002]; //stiva
vector<int> v[nmax]; //listele de adiacenta
void read()
{
int i,x,y;
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
nrv[x]++;
nrv[y]++;
v[x].push_back(y);
v[y].push_back(x);
}
}
void df(int nod,int tata)
{
int i,fiu,x1,x2;
timp++;
d[nod]=timp;
sus[nod]=timp;
for(i=0;i<nrv[nod];i++)
{
fiu=v[nod][i];
if(!d[fiu])
{
k++;
s[k].x=nod;
s[k].y=fiu;
if(nod==start)
nrfii++;
df(fiu,nod);
if(sus[fiu]>=d[nod]) // nodul este punct de articulatie
if(tata!=-1)
{
nrc++;
pp[nrc]=1+hh;//
do
{
x1=s[k].x;
x2=s[k].y;
hh++;
w[hh]=s[k];
k--;
}
while (x1!=nod || x2!=fiu);
}
if(sus[fiu]<sus[nod])
sus[nod]=sus[fiu];
}
else
if(fiu!=tata)
if(sus[fiu]<sus[nod])
sus[nod]=sus[fiu];
}
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
timp=0;
nrfii=0;
start=1;
df(1,-1);
while (k>0)
{
nrc++;
pp[nrc]=1+hh;
do
{
x1=s[k].x;
x2=s[k].y;
hh++;
w[hh]=s[k];
k--;
}
while(x1!=1 && x2!=1);
}
pp[nrc+1]=1+hh;
printf("%d\n",nrc);
for (int k=1;k<=nrc;k++)
{
p1=n+1;
p2=0;
for (int j=pp[k];j<pp[k+1];j++)
{
x1=w[j].x;
x2=w[j].y;
xx[x1]=1;
xx[x2]=1;
if (x1<p1)p1=x1;
if (x2<p1)p1=x2;
if (x1>p2)p2=x1;
if (x2>p2)p2=x2;
}
for (int j=p1;j<=p2;j++)
if (xx[j]!=0)
{
printf("%d ",j);
xx[j]=0;
}
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}