Cod sursa(job #2190312)

Utilizator gundorfMoldovan George gundorf Data 30 martie 2018 15:11:43
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
// Componente_Biconexe.cpp : Defines the entry point for the console application.
//

#include <vector>
#include <fstream>
#include <utility>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define Nmax 100002

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

void Citire(vector <int> v[], int &n,int &m)
{
	int i,x,y;
	fin >> n>>m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
}

int compBi; //numarul de componente biconexe
void Afisare(vector<pair<int, int>>sol[])
{
	fout << compBi << "\n";
	for (int i = 1; i <= compBi; i++)
	{
		unordered_map <int, int> viz1;
		for (pair<int, int> it : sol[i])
		{
			if (viz1[it.first] != 1998) fout << it.first << " ";

			if (viz1[it.second] != 1998) fout << it.second << " ";

			viz1[it.first] = viz1[it.second] = 1998;
		}
		fout << "\n";
	}

}




int nivel[Nmax], nivel_minim[Nmax];
int viz[Nmax];
stack <pair<int, int>> s1;// stiva cu muchii
vector <pair<int, int>>sol[Nmax]; //vector de vectori de muchii ca sa afisez componentele biconexe
void Componente_Biconexe(int x,vector <int> v[])
{
	viz[x] = 1;
	nivel_minim[x] = nivel[x];
	for (int it : v[x])
	{
		if (viz[it] == 0) //daca e muchie de avansare
		{
			s1.push({ x,it });
			nivel[it] = nivel[x] + 1;

			Componente_Biconexe(it, v);

			nivel_minim[x] = min(nivel_minim[x], nivel_minim[it]);//actualizez nivelul minim pt nodul x

			if (nivel[x] <= nivel_minim[it]) //inseamna ca muchia (x, it) e critica, deci x e nod critic
			{
				compBi++; //cresc nr ce componente biconexe
				//afisez componenta biconexa
				//vector <pair<int, int>>sol;
				pair<int, int> w = { x,it };
				while (s1.top()!=w)
				{
					sol[compBi].push_back(s1.top());
					s1.pop();

				}
				sol[compBi].push_back(s1.top());
				s1.pop();

			}
		}
		else
			if (nivel[it] < nivel[x] - 1) //daca e muchie de intoarcere
				nivel_minim[x] = min(nivel_minim[x], nivel[it]); //actualizez nivelul minim de intoarcere al lui x
	}

}
int main()
{
	vector <int> v[Nmax];
	int n, m;
	Citire(v, n, m);
	nivel[1] = 1;
	Componente_Biconexe(1, v);
	Afisare(sol);
    return 0;
}