Cod sursa(job #726717)

Utilizator dragosnicolaeNicolae Dragos dragosnicolae Data 27 martie 2012 14:17:01
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
stack < pair <int,int> > s;
vector <int> l[100005],c[100005];
int niv[100005],nivmin[100005],t[100005],n,m,nr;
void cit(){
	FILE *f;
	int i,a,b;
	f=fopen("biconex.in","r");
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++){
		fscanf(f,"%d%d",&a,&b);
		l[a].push_back(b);
		l[b].push_back(a);
	}
	fclose(f);
}
void comp_biconexa(int a,int b){
	int x,y;
	nr++;
	do{
		x=s.top().first;
		y=s.top().second;
		s.pop();
		c[nr].push_back(x);
		c[nr].push_back(y);
	}while(x!=a||y!=b);
}
void df(int k){
	nivmin[k]=niv[k];
	for(unsigned int i=0;i<l[k].size();i++)
		if(niv[l[k][i]]==0){
			niv[l[k][i]]=niv[k]+1;
			t[l[k][i]]=k;
			s.push(make_pair(k,l[k][i]));
			df(l[k][i]);
			if(nivmin[l[k][i]]<nivmin[k])
				nivmin[k]=nivmin[l[k][i]];
			if(nivmin[l[k][i]]>=niv[k])
				comp_biconexa(k,l[k][i]);
		}else
			if(l[k][i]!=t[k])
				if(niv[l[k][i]]<nivmin[k]){
					s.push(make_pair(k,l[k][i]));
					nivmin[k]=niv[l[k][i]];
				}
}
void afis(){
	int i;
	FILE *f;
	f=fopen("biconex.out","w");
	fprintf(f,"%d\n",nr);
	for(i=1;i<=nr;i++){
		sort(c[i].begin(),c[i].end());
		c[i].erase(unique(c[i].begin(),c[i].end()),c[i].end());
		for(unsigned int j=0;j<c[i].size();j++)
			fprintf(f,"%d ",c[i][j]);
		fprintf(f,"\n");
	}
	fclose(f);
}
int main(){
	cit();
	niv[1]=1;
	df(1);
	afis();
	return 0;
}