Cod sursa(job #1033034)

Utilizator RobertSSamoilescu Robert RobertS Data 16 noiembrie 2013 13:08:44
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.37 kb
#include<vector>
#include<iostream>
#include<fstream>

using namespace std;

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


#define MAX_N 100000

int n, m;
vector<int> list[MAX_N];
vector<int> st[2];

bool viz[MAX_N];

vector<int> biconex[MAX_N];
int contor = -1;

void citeste(){
	fin >> n >> m;
	
	int a, b;
	for(int i=1; i<=m; i++){
		fin >> a >> b;
		list[a].push_back(b);
		list[b].push_back(a);
	}

}

bool in_lista(int nod1, int nod2){ // verifica daca nodul2 se afla in lista de adiacenta a nodului1
	for(size_t i=0; i< list[nod1].size(); i++){
		if(list[nod1][i] == nod2) return true;
	}
	
	return false;
} 



int muchie_intoarcere(int nod){ // verifica daca exista muchie de intoarcere de la nod la un alt nod in stiva
	for(size_t i=0; i<st[0].size()-2; i++){
		if(in_lista(nod, st[0][i])){
			return i; // returneaza nivelul pe care se afala nodul ce prezinta muchia de intoarcere
		}
	}
	
	return -1;
}

void afis_u2(){
	int lung = st[0].size();
	if(lung > 1)
		if(st[1][lung-1] == 0){
			contor ++;
			biconex[contor].push_back(st[0][lung-2]);
			biconex[contor].push_back(st[0][lung-1]);
			
		}
	
	st[0].pop_back();
	st[1].pop_back();
	
}


void afis(int niv){
	contor ++;
	for(size_t i=niv; i<st[0].size(); i++){
		biconex[contor].push_back(st[0][i]);
		
	}
	
	st[0].erase(st[0].begin() + niv + 1, st[0].end()-1);
	st[1].erase(st[1].begin() + niv + 1, st[1].end()-1);
	
	int lung = st[1].size();
	st[1][lung-1] = 1;
	
}

void df(int nod){
	if(!viz[nod]){
		viz[nod] = 1;
		st[0].push_back(nod);
		st[1].push_back(0);
	}
	if(st[0].size() > 2){
		int niv = muchie_intoarcere(nod);
		
		if(niv > (-1) ){
			afis(niv);
		}
		
	}
	
	bool gasit = false; // daca de la nod se poate merge mai departe
	int nod2 = -1;
	
	for(size_t i=0; i<list[nod].size(); i++){
		int x = list[nod][i];
		if(!viz[x]) {
			nod2 = x;
			gasit = true;
			break;
		}
	}
	

	if(!gasit){
		afis_u2();
		int lung = st[0].size();
		int nod3 = -1;
		if(lung > 0){
			nod3 = st[0][lung-1];
			df(nod3);
		}
	}else{
			df(nod2);
	}
	
	
}


int main(){
	citeste();
	for(int i=1; i<=n; i++){
		if(!viz[i]) df(i);
	}
	
	fout << contor + 1 << '\n';
	for(int i=0; i<=contor; i++){
		for(size_t j=0; j<biconex[i].size(); j++){
			fout << biconex[i][j] << " ";
		}
		fout << '\n';
	}
	
return 0;
}