Cod sursa(job #1127002)

Utilizator fhandreiAndrei Hareza fhandrei Data 27 februarie 2014 10:46:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.89 kb
// Include
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;

// Definitii
#define pb push_back
#define edge_t pair<int, int>
#define mp make_pair

// Constante
const int sz = (int)1e5+1;

// Functii
void dfs(int node, int father=-1, int level=1); // Nodul curent, tatal lui si adancimea lui in arborele dfs
void biconex(edge_t stop);

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

int nodes, edges;

// Nivelul minim la care poti ajunge din nodul i pe un drum "in jos" si apoi printr-o
// muchie de intoarcere in arborele dfs (mai exact, pe un alt drum decat cel pe care-a venit)
// Voi presupune ca daca minLevel e 0, nodul nu a fost vizitat, iar daca e diferit de 0, a fost
int minLevel[sz]; 

vector<int> graph[sz]; // Graful, reprezentat cu liste de adiacenta

// Stiva unde retin muchiile din parcurgerea in adancime
stack<edge_t> edgesStack;

vector< set<int> > answers;

// Main
int main()
{
	in >> nodes >> edges;
	
	int rFrom, rTo;
	while(edges--)
	{
		in >> rFrom >> rTo;
		graph[rFrom].pb(rTo);
		graph[rTo].pb(rFrom);
	}
	
	dfs(1);
	
	out << answers.size() << '\n';
	
	vector< set<int> >::iterator it, end=answers.end();
	for(it=answers.begin() ; it!=end ; ++it)
	{
		set<int>::iterator sit, send=it->end();
		for(sit=it->begin() ; sit!=send ; ++sit)
			out << *sit << ' ';
		out << '\n';
	}
	
	in.close();
	out.close();
	return 0;
}

void dfs(int node, int father, int level)
{
	// Initial, nivelul minim este egal cu nivelul nodului
	minLevel[node] = level;
	
	// Iau toti vecinii nodului curent
	vector<int>::iterator it, end=graph[node].end();
	for(it=graph[node].begin() ; it!=end ; ++it)
	{
		// Nu iau in calcul nodul din care-am venit
		if(*it == father)
			continue;
		
		// Daca nodul a fost deja vizitat, sunt pe o muchie de intoarcere si vad la ce nivel pot ajunge prin ea
		if(minLevel[*it])
		{
			minLevel[node] = min(minLevel[node], minLevel[*it]);
			continue;
		}
		
		// Pun muchia in stiva pentru a putea gasi raspunsul
		edgesStack.push(mp(node, *it));
		
		// Fac parcurgere in adancime din vecin, considerand nodul curent tata
		// si nivelul cu 1 mai mare decat al nodului curent
		dfs(*it, node, level+1);
		
		// Vad la ce nivel minim pot plecand pe drumul "in jos" prin vecinul curent (*it)
		minLevel[node] = min(minLevel[node], minLevel[*it]);
		
		// Daca nu exista niciun alt drum prin care vecinul curent (*it) poate ajunge, in arborele dfs,
		// deasupra de nodul curent, am gasit o componenta biconexa
		if(level <= minLevel[*it])
			biconex(mp(node, *it));
	}
}

void biconex(edge_t stop)
{
	edge_t currentEdge;
	set<int> answer;
	do
	{
		currentEdge = edgesStack.top();
		edgesStack.pop();
		
		answer.insert(currentEdge.first);
		answer.insert(currentEdge.second);
		
	} while (currentEdge != stop);
	
	answers.pb(answer);
}