Cod sursa(job #629198)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 2 noiembrie 2011 20:44:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("biconex.in");
ofstream out("biconex.out");

const int N=100001;
const int M=200001;

struct muchie{
	int a,b;
}ordinedf[M];

vector <int> muchii[N],solutii[N];
int nivm[N],niv[N];// nivelul mminim la care se poate ajunge pe un drum in jos si apoi pe muchie de intoarecere. este initializat cu nivelului sau; nivelul N
int n,m,nrmuchiidf,nrbiconexe;//numarul de muchii de arbore parcurse deja de df
bool viz[N];//vectorul de vizitat asociat df-ului

int minimim(int a,int b){
	return a<b;
}

void citiremuchii(){
	int i,a,b;
	for(i=1;i<=m;i++){
		in>>a>>b;
		muchii[a].push_back(b);
		muchii[b].push_back(a);
	}
}

void update(int x,int y){
	nrbiconexe++;
	while(ordinedf[nrmuchiidf].a!=x && ordinedf[nrmuchiidf].b!=y){
		solutii[nrbiconexe].push_back(ordinedf[nrmuchiidf].b);
		nrmuchiidf--;
	}
	solutii[nrbiconexe].push_back(ordinedf[nrmuchiidf].b);
	solutii[nrbiconexe].push_back(ordinedf[nrmuchiidf].a);
	nrmuchiidf--;
}

void df(int x,int parinte){
	int i,y;
	viz[x]=true;
	nivm[x]=niv[parinte]+1;
	niv[x]=niv[parinte]+1;
	for(i=0;i<muchii[x].size();i++){
		y=muchii[x][i];
		if(!viz[y]){
			nrmuchiidf++;
			ordinedf[nrmuchiidf].a=x;
			ordinedf[nrmuchiidf].b=y;
			df(y,x);
			if(niv[x]<=nivm[y]){
				update(x,y);
			}
			nivm[x]=min(nivm[x],nivm[y]);
			continue;
		}
		else{
			if(y!=parinte)
				nivm[x]=min(nivm[x],niv[y]);
		}
	}
}
		

void solve(){
	int i;
	for(i=1;i<=n;i++){
		if(!viz[i]){
			df(i,1);
		}
	}
}

int main(){
	int i,j;
	in>>n>>m;
	citiremuchii();
	solve();
	out<<nrbiconexe<<"\n";
	for(i=1;i<=n;i++){
		for(j=solutii[i].size()-1;j>=0;j--){
			out<<solutii[i][j]<<" ";
		}
		out<<"\n";
	}
	return 0;
}