Pagini recente » Cod sursa (job #923686) | Cod sursa (job #733018) | Cod sursa (job #164362) | Cod sursa (job #1505460) | Cod sursa (job #3269795)
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
// struct ComponentaBiconexa
// {
// set<int> noduri;
// vector<pair<int, int>> muchii;
// };
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
vector<set<int>> la;
set<int> noduri_critice;
vector<bool> viz;
vector<int> nivel_min, nivel;
// vector<ComponentaBiconexa> componente_biconexe;
vector<set<int>> componente_biconexe;
stack<pair<int, int>> stiva_componente_biconexe;
void Read()
{
f >> n >> m;
la.resize(n + 1);
nivel_min.resize(n + 1, 0);
nivel.resize(n + 1, 0);
viz.resize(n + 1, false);
for (int i = 1; i <= m; i++)
{
int x, y;
f >> x >> y;
la[x].insert(y);
la[y].insert(x);
}
}
void df(int nod_curent)
{
viz[nod_curent] = true;
nivel_min[nod_curent] = nivel[nod_curent];
int copii = 0;
for (auto &vecin : la[nod_curent])
{
if (viz[vecin] == 0)
{
copii++;
nivel[vecin] = nivel[nod_curent] + 1;
stiva_componente_biconexe.push({nod_curent, vecin});
df(vecin);
nivel_min[nod_curent] = min(nivel_min[nod_curent], nivel_min[vecin]);
// avem componentă biconexă
if (nivel_min[vecin] >= nivel[nod_curent])
{
auto &componenta = componente_biconexe.emplace_back();
while (stiva_componente_biconexe.top() != make_pair(nod_curent, vecin))
{
auto &pereche = stiva_componente_biconexe.top();
stiva_componente_biconexe.pop();
componenta.insert(pereche.first);
componenta.insert(pereche.second);
}
auto &pereche = stiva_componente_biconexe.top();
stiva_componente_biconexe.pop();
componenta.insert(pereche.first);
componenta.insert(pereche.second);
}
}
else if (nivel[vecin] < nivel[nod_curent] - 1)
{
nivel_min[nod_curent] = min(nivel_min[nod_curent], nivel[vecin]);
stiva_componente_biconexe.push({nod_curent, vecin});
}
}
}
int main()
{
Read();
nivel[1] = 1;
df(1);
g << componente_biconexe.size() << '\n';
for (auto &componenta : componente_biconexe)
{
for (auto &nod : componenta)
{
g << nod << ' ';
}
g << '\n';
}
return 0;
}