Pagini recente » Cod sursa (job #2751802) | Borderou de evaluare (job #1032912) | Rating falico (falicos) | Cod sursa (job #1795214) | Cod sursa (job #782288)
Cod sursa(job #782288)
#include<fstream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef struct lnod{
int vf;
struct lnod *next;
}*Nod;
const int NM=100005;
int N,M,stx[NM+NM],sty[NM+NM],vf,nrC;
int dfn[NM],l[NM];
Nod a[NM],C[NM];
bool viz[NM];
void add(Nod &q,int x){
Nod p=new lnod;
p->vf=x;
p->next=q;
q=p;
}
void comp(int x,int y){
int dx,dy;
++nrC;
do{
dx=stx[vf]; dy=sty[vf--];
add(C[nrC],dx); add(C[nrC],dy);
}while(dx!=x || dy!=y);
}
void dfs(int nod,int last,int num){
dfn[nod]=l[nod]=num;
for(Nod p=a[nod];p;p=p->next)
{
if(p->vf==last)continue;
if(dfn[p->vf]==-1)
{
stx[++vf]=nod; sty[vf]=p->vf;
dfs(p->vf,nod,num+1);
l[nod]=min(l[nod],l[p->vf]);
if(l[p->vf] >= dfn[nod])
comp(nod,p->vf);
}
else l[nod]=min(l[nod],dfn[p->vf]);
}
}
int main(void){
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int i,x0,y0;
fin>>N>>M;
for(i=1;i<=M;++i)
{
fin>>x0>>y0;
add(a[x0],y0);
add(a[y0],x0);
}
memset(dfn,-1,sizeof(dfn));
dfs(1,0,0);
fout<<nrC<<'\n';
for(i=1;i<=nrC;++i)
{
x0=0;
for(Nod p=C[i];p;p=p->next)
dfn[++x0]=p->vf;
sort(dfn+1,dfn+x0+1);
for(y0=1;y0<=x0;++y0)
if(dfn[y0]!=dfn[y0-1])fout<<dfn[y0]<<' ';
fout<<'\n';
}
return 0;
}