Cod sursa(job #1586745)

Utilizator blackoddAxinie Razvan blackodd Data 1 februarie 2016 17:08:12
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

#define pb push_back
#define MaxN 100001

int n, m;

vector<int> L(MaxN), niv(MaxN);
vector<bool> viz(MaxN);
vector<int> G[MaxN];

stack<pair<int,int> >_stack;
vector<vector<int> >components;

void Read();
void Df(int, int);
void GetComponent(int, int);
void Write();

int main() {
	
	Read();
	Df(1,0);
	Write();
	
	fin.close();
	fout.close();
	return 0;
}

void Write() {
	
	fout << components.size() << '\n';
	
	for ( auto comp : components ) {
		sort(comp.begin(), comp.end() );
		comp.erase(unique(comp.begin(), comp.end()), comp.end() );
		for ( const auto c : comp )
			fout << c << ' ';
		fout << '\n';
	}
}

void Df(int nod, int father) {
	
	L[nod] = niv[nod] = niv[father] + 1;
	
	viz[nod] = true;
	
	for ( const int x : G[nod] ) {
		if ( x == father) 
			continue;
		if ( !viz[x] ) {
			_stack.push({x,nod}); // fiul si tatal <3
			Df(x, nod);
			L[nod] = min(L[nod], L[x]);
			if ( L[x] >= niv[nod] ) 
				GetComponent(x, nod);
			}
		else // back edge sanchi
			L[nod] = min(L[nod], niv[x]);
		}
					
}

void GetComponent(int x, int father) {
	vector<int> c;
	int y, y_father;
	do {
		y = _stack.top().first;
		y_father = _stack.top().second;
		_stack.pop();
		c.pb(y);
		c.pb(y_father);
	}while( y != x && y_father != father && !_stack.empty() );
	
	components.pb(c);
}
		

void Read() {
	
	fin >> n >> m;
	
	int x, y;
	
	while(m--) {
		fin >> x >> y;
		G[x].pb(y);
		G[y].pb(x);
	}
}