Cod sursa(job #648030)

Utilizator cristicecCristian Uricec cristicec Data 12 decembrie 2011 22:24:33
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<iostream>
#include<fstream>
#include<vector>

using namespace std;


vector <int> lista[100003];
vector <int> comp[100003];
int n , m;
int nivelul_min[100003], nivelul_dfs[100003], viz[100003], stiva_tata[100003] , stiva_fiu[100003];
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( unsigned int i = 0 ; i< lista[nod].size(); i++)
		if(viz[lista[nod][i]]==1)
			nivelul_min[nod] = min( nivelul_min[nod], nivelul_dfs[lista[nod][i]]);
		else{
			nivelul_dfs[lista[nod][i]] = nivelul_dfs[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[j].size();i++){
			fout<<comp[k][i]<<" ";
		}
	fout<<endl;
	}
	return 0;
}