Pagini recente » Cod sursa (job #673537) | Cod sursa (job #530078) | Cod sursa (job #540955) | Cod sursa (job #1531261) | Cod sursa (job #2981175)
#include <bits/stdc++.h>
using namespace std;
string np = "biconex";
ifstream f(np + ".in");
ofstream g(np + ".out");
// #define f cin
// #define g cout
int n, m, radacina, t[100003], nivel[100003], nma[100003];
bool viz[100003], p_art[100003];
vector<int> adj[100003];
vector<pair<int, int>> punti;
vector<vector<int>> comp_bicon;
stack<int> st;
void dfs(int nod, int tata)
{
viz[nod] = 1;
nivel[nod] = nma[nod] = nivel[tata] + 1;
st.push(nod); // pt det comp biconex
int nrfii = 0;
for (auto next : adj[nod])
if (next != tata)
{
if (viz[next])
nma[nod] = min(nma[nod], nivel[next]);
else
{
nrfii++;
dfs(next, nod);
nma[nod] = min(nma[nod], nma[next]);
// det punti
if (nivel[nod] < nma[next])
punti.push_back({nod, next});
if (nivel[nod] <= nma[next])
{
// det puncte articulatie
if (nod != radacina)
p_art[nod] = 1;
// det componente biconexe
vector<int> aux;
while (st.top() != next)
aux.push_back(st.top()), st.pop();
aux.push_back(next);
st.pop();
aux.push_back(nod);
comp_bicon.push_back(aux);
}
}
}
if (nod == radacina and nrfii > 1)
p_art[nod] = 1;
}
int main()
{
// f >> cer;
f >> n >> m;
for (int i = 1, a, b; i <= m; i++)
f >> a >> b,
adj[a].push_back(b), adj[b].push_back(a);
radacina = 1;
dfs(1, 0);
// if (cer == 1)
// {
g << comp_bicon.size() << '\n';
for (int i = 0; i < comp_bicon.size(); i++, g << '\n')
{
// g << comp_bicon[i].size() << " ";
for (auto x : comp_bicon[i])
g << x << " ";
}
// }
// else if (cer == 2)
// {
// int rez = 0;
// for (int i = 1; i <= n; i++)
// if (p_art[i] == 1)
// rez++;
// g << rez << '\n';
// for (int i = 1; i <= n; i++)
// if (p_art[i] == 1)
// g << i << " ";
// }
// else
// {
// g << punti.size() << '\n';
// for (auto x : punti)
// g << x.first << " " << x.second << '\n';
// }
return 0;
}