Cod sursa(job #469315)

Utilizator S7012MYPetru Trimbitas S7012MY Data 7 iulie 2010 15:07:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
#define DN 100005
using  namespace std;

int low[DN],dfn[DN],cont;
vector <vector <int> > sol; 
stack <pair <int, int> > stiva;
struct nod {
	int x;
	nod *urm;
} *v[DN];

void adaugare(int x,int y) {
	nod *p;
	p=new nod;
	p->x=y;
	p->urm=v[x];
	v[x]=p;
}

void afis(int x,int y) {
	int a,b;
	vector <int> componenta;
	do {
		a=stiva.top().first;
		b=stiva.top().second;
		stiva.pop();
		componenta.push_back(a);
		componenta.push_back(b);
	}while (a!=x || b!=y);
	sol.push_back(componenta);
}

void biconex(int n,int fn, int nr) {
	nod *p;
	dfn[n]=low[n]=nr;
	for(p=v[n];p!=NULL; p=p->urm) {
		if(p->x==fn) continue;
		if(dfn[p->x]==-1) {//nu a fost viz
			stiva.push(make_pair(n,p->x));
			biconex(p->x,n,nr+1);
			low[n]=min(low[n],low[p->x]);
			if(low[p->x]>=dfn[n])
				++cont,afis(n,p->x);
		}
		else low[n] = min(low[n], dfn[p->x]);
	}
}

void afisare(int n) {
    nod *p;
    int k;
    for(k=1; k<=n; k++) {
        p=v[k];
        printf("%d:",k);
        while(p) {
            printf("%d ",p->x);
            p=p->urm;
        }
        printf("\n");
    }
}


int main()
{
	int i,x,y,n,m;
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1; i<=m; i++) {
		scanf("%d %d",&x,&y);
		adaugare(x,y);
		adaugare(y,x);
	}
	//afisare(n);
	memset(dfn,-1,sizeof(dfn));
	biconex(1,0,0);
	printf("%d\n",cont);
	for(i=0; i<sol.size(); i++) {
		sort(sol[i].begin(),sol[i].end());
		sol[i].erase(unique(sol[i].begin(), sol[i].end()), sol[i].end());
		for (size_t j = 0; j < sol[i].size(); ++ j)
			printf("%d ",sol[i][j]);
		printf("\n");
	}
	return 0;
}