Pagini recente » Cod sursa (job #3322978) | Cod sursa (job #3321206) | Cod sursa (job #3342380) | Cod sursa (job #3352200) | Cod sursa (job #3307004)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int NMAX = 100001;
vector<int> G[NMAX];
vector<vector<int>> compBiconexe;
int nivel[NMAX], nivelMinim[NMAX];
void addCompBiconexa(int x, int parent, stack<int> &S)
{
/// parent este nodul critic
vector<int> componenta{parent};
int vf;
do
{
vf = S.top();
componenta.push_back(vf);
S.pop();
} while (vf != x);
compBiconexe.push_back(componenta);
}
void DFS(int x, int parent, stack<int> &S)
{
S.push(x);
nivel[x] = nivel[parent] + 1; /// l-am vizitat
nivelMinim[x] = nivel[x];
for (auto vec: G[x])
{
if (vec == parent)
continue;///nu vreau sa ma intorc in parinte
if (nivel[vec] == 0) /// am descoperit un nod nou
{
DFS(vec, x, S);
/// am terminat parcurgerea in sub-tree
if (nivelMinim[vec] >= nivel[x]) /// copilul nu poate ajunge mai sus de parinte
{
/// inseamna ca x este nod critic
addCompBiconexa(vec, x, S);
}
nivelMinim[x] = min(nivelMinim[x],
nivelMinim[vec]); /// daca copilul reuseste sa urce mai sus de x, atunci si x o puate lua pe ac drum
/// altfel nu este nod critic deci nu il procesez acum
}
else
{
/// avem muchie de intoarcere
nivelMinim[x] = min(nivelMinim[x], nivel[vec]);
}
}
}
int main()
{
int n, m;
f >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
f >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
stack<int> S;
DFS(1, 0, S);
g << compBiconexe.size() << '\n';
for (auto comp: compBiconexe)
{
for (auto node: comp)
{
g << node << ' ';
}
g << '\n';
}
return 0;
}