Cod sursa(job #648008)

Utilizator cristicecCristian Uricec cristicec Data 12 decembrie 2011 21:51:21
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<fstream>
#include<vector>

using namespace std;

#define NMAX 100003

int n , m;
int nivelul_min[NMAX], nivelul_dfs[NMAX], viz[NMAX];
int stiva_tata[NMAX] , stiva_fiu[NMAX];
vector lista[NMAX];
vector comp[NMAX];
int vf;
int k;

inline int min( int a, int b ){
	if(a>b) return b;
	return a;
}

void dfs(int nod){
	viz[nod]=1;
	nivelul_min[nod]=nivelul_dfs[nod];
	
	for(int i = 0 ; i< lista[nod].end(); i++)
		if(viz[lista[nod][i]]==1)
			nivelul_min[nod] = min( nivelul_min[nod], nivelul_bfs[lista[nod][i]]);
		else{
			nivelul_bfs[lista[nod][i]] = nivelul_bfs[nod]+1;
			vf++;
			stiva_tata[vf]=nod;
			stiva_fiu[vf]=lista[nod][i];
			dfs(stiva_fiu[vf]);
			
			if(nivelul_min[lista[nod][i]] >= nivelul_dfs[nod]){ //comp
				k++;
				while( stiva_tata[vf]!=nod && stiva_fiu[vf]!=lista[nod][i]){
					comp[k].push_back(stiva_fiu[vf]);
					vf--;
				}
				
				comp[k].push_back(stiva_tata[vf]);
				comp[k].push_back(stiva_fiu[vf]);
				vf--;
			}
			
			nivelul_min[nod] = min ( nivelul_min[nod], nivelul_min[lista[nod][i]] );
				

		}
}		
	

int main(){
	ifstream fin("biconex.in");
	ofstream fout("biconex.out");
	fin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++){
		fin>>x>>y;
		lista[x].push_back(y);
		lista[y].push_back(x);
	}
	
	dfs(1);
	
	fout<<k<<endl;
	for(int j=1;j<=k;j++){
		
		for(int i=0;i<comp[k].end();i++){
			fout<<comp[k][i]<<" ";
		}
	fout<<endl;
	}
	return 0;
}