Pagini recente » Cod sursa (job #2305239) | Cod sursa (job #1506781) | Cod sursa (job #1595289) | Cod sursa (job #2572424) | Cod sursa (job #315101)
Cod sursa(job #315101)
#include<stdio.h>
#define NMAX 100003
#define INF 333333
#define ROOT 1
struct lista {
int x;
lista *next;
};
struct muchie {
int x,y;
};
lista *v[NMAX],*comp[NMAX];
muchie s[NMAX];
int ind[NMAX],t[NMAX],mr[NMAX],id=0,i,ns=0,nc=0,n,m,rc=0;
void adauga(lista* &l,int y) {
lista *q=new lista;
q->x=y;
q->next=l;
l=q;
}
void adaugaMuchie(int x,int y) {
s[++ns].x=x;
s[ns].y=y;
}
void scoateMuchie(int &x,int &y) {
x=s[ns].x;
y=s[ns--].y;
}
void memoreazaComponenta(int x,int y) {
int xx,yy;
comp[nc]=NULL;
do {
scoateMuchie(xx,yy);
adauga(comp[nc],yy);
} while(((xx!=x)||(yy!=y)));
adauga(comp[nc++],x);
}
void citeste() {
int i,x,y;
freopen("biconex.in","r",stdin);
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++) {
v[i]=NULL;
ind[i]=0;
t[i]=-1;
mr[i]=INF;
}
for(i=0;i<m;i++) {
scanf("%d %d",&x,&y);
adauga(v[x],y);
adauga(v[y],x);
}
fclose(stdin);
}
void biconex(int nod) {
ind[nod]=++id;
lista *q=v[nod];
int im=INF,ic=INF;
while(q) {
if(t[nod]!=q->x)
if(ind[q->x]) {
if((ind[q->x]<ind[nod])&&(ind[q->x]<ic)) ic=ind[q->x];
}
else {
t[q->x]=nod;
adaugaMuchie(nod,q->x);
biconex(q->x);
if(mr[q->x]<im) im=mr[q->x];
if((nod==ROOT)&&(id<n)) rc=1;
if((mr[q->x]>=ind[nod])||(rc&&(nod==ROOT))) memoreazaComponenta(nod,q->x);
}
q=q->next;
}
mr[nod]=im<ic?im:ic;
}
void scrie() {
lista *q;
freopen("biconex.out","w",stdout);
printf("%d\n",nc);
for(int i=0;i<nc;i++) {
q=comp[i];
while(q) {
printf("%d ",q->x);
q=q->next;
}
printf("\n");
}
fclose(stdout);
}
int main() {
citeste();
biconex(ROOT);
scrie();
return 0;
}