Pagini recente » Cod sursa (job #1777116) | Cod sursa (job #1610986) | Cod sursa (job #1260319) | Cod sursa (job #364456) | Cod sursa (job #2190312)
// 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;
}