Pagini recente » Cod sursa (job #2415685) | Cod sursa (job #1052217) | Cod sursa (job #3171267) | Cod sursa (job #296123) | Cod sursa (job #2540107)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int Nmax = 10e5 + 5;
typedef pair <int, int> ipair;
vector <int> adj[Nmax], solution[Nmax], niv, low;
stack <ipair> stiva;
int n, m, nocomp;
static inline void addsolution(int x, int y)
{
while(true)
{
int fir = stiva.top().first;
int sec = stiva.top().second;
solution[nocomp].push_back(fir);
solution[nocomp].push_back(sec);
stiva.pop();
if(fir == x && sec == y)
break;
}
sort(solution[nocomp].begin(), solution[nocomp].end());
}
static inline void dfs(int nod, int parent, int lvl)
{
niv[nod] = low[nod] = lvl;
for(auto i : adj[nod])
{
if(i == parent) // daca nodul urmator este tatal nodului curent
continue; // treci mai departe
if(!low[i]) // daca nodul urmator nu a fost vizitat inca
{
stiva.push({nod, i}); // adaug pe stiva muchia care face parte din componenta biconexa componenta biconexa
dfs(i, nod, lvl + 1); // continui cu dfs din nodul urmator
low[nod] = min(low[nod], low[i]); // nivelul minim la care se poate ajunge din nodul curent prin descendenti
if(niv[nod] <= low[i]) // daca nici un descendent al nodului curent nu poate ajunge mai sus de el
{
++ nocomp; // creste numarul componentelor biconexe
addsolution(nod, i); // adaug solutia
}
}
else // daca nodul urmator a fost vizitat anterior
low[nod] = min(low[nod], niv[i]); // gasesc nivelul minim la care pot ajunge din nodul meu curent prin toti descendentii lui
}
}
void output()
{
out << nocomp << '\n';
for(auto i = 1; i <= nocomp; ++ i)
{
for(auto& j : solution[i])
if(*(&j + 1) != j)
out << j << ' ';
out << '\n';
}
}
int main()
{
in.tie(0);
in >> n >> m;
niv.resize(n + 1);
low.resize(n + 1, 0);
while(m --)
{
int x, y;
in >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1, 0, 1);
output();
return 0;
}