Pagini recente » Cod sursa (job #1025465) | Cod sursa (job #647319) | Cod sursa (job #1228660) | Cod sursa (job #2942724) | Cod sursa (job #280539)
Cod sursa(job #280539)
#include<stdio.h>
#include<string.h>
#define N 100010
FILE *f=fopen("biconex.in","r");
FILE *g=fopen("biconex.out","w");
struct NOD {
int x;
NOD* urm;
};
NOD *G[N],*C[N];
int n,m,prim,ultim;
int S[5*N];
int D[N],L[N],ord,nr;
char viz[N];
void ADD(NOD*&p,int catre){
NOD *q= new NOD;
q->urm=p;
q->x=catre;
p=q;
}
void date(){
int x,y;
fscanf(f,"%d%d",&n,&m);
for(;m--;){ fscanf(f,"%d%d",&x,&y);ADD(G[x],y);ADD(G[y],x); }
S[++ultim]=1;
S[++ultim]=-1;
memset(D,-1,sizeof(D));
memset(L,-1,sizeof(L));
}
inline int min(int a,int b){ return (a<b?a:b); }
void Formeaza(int x,int y){
nr++;
int s1,s2;
do{
s1 = S[ultim--];
s2 = S[ultim--];
NOD *q= new NOD;
q->x = s1;
q->urm = C[nr];
C[nr]=q;
q=new NOD;
q->x = s2;
q->urm=C[nr];
C[nr]=q;
}while(s1!=x || s2!=y);
}
void biconex(int nod, int tnod){
D[nod]=L[nod]=++ord;
NOD*q = new NOD;
q = G[nod];
for(;q;q=q->urm){
if(q->x != tnod && D[q->x]<D[nod]){
S[++ultim]=nod;
S[++ultim]=q->x;
}
if(D[q->x]==-1) {
biconex(q->x,nod);
L[nod] = min(L[nod],L[q->x]);
if(L[q->x]>=D[nod]){
Formeaza(q->x,nod);
}
}else{
if(q->x != tnod) L[nod]=min(L[nod],D[q->x]);
}
}
}
int main(){
date();
biconex(1,-1);
fprintf(g,"%d\n",nr);
NOD*q = new NOD;
for(int i=1;i<=nr;i++){
for(q=C[i];q;q=q->urm)viz[q->x]='1';
for(q=C[i];q;q=q->urm)
if(viz[q->x]=='1'){
fprintf(g,"%d ",q->x);viz[q->x]='0';}
fprintf(g,"\n");
}
return 0;
}