Mai intai trebuie sa te autentifici.
Cod sursa(job #3364662)
| Utilizator | Data | 8 septembrie 2026 20:09:55 | |
|---|---|---|---|
| Problema | Componente biconexe | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.66 kb |
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100005;
int n, m;
vector<int> la[NMAX];
int bcc_cnt = 0;
set<int> bcc[NMAX];
int disc[NMAX];
int low[NMAX];
int parent[NMAX];
int t = 1;
stack<pair<int, int>> stiva;
void dfs(int nod)
{
disc[nod] = low[nod] = t++;
for (auto &c: la[nod])
{
if (c == parent[nod])
continue;
if (!disc[c])
{
parent[c] = nod;
stiva.push(make_pair(nod, c));
dfs(c);
low[nod] = min(low[nod], low[c]);
if (disc[nod] <= low[c])
{
++bcc_cnt;
while (stiva.top() != make_pair(nod, c))
{
bcc[bcc_cnt].insert(stiva.top().first);
bcc[bcc_cnt].insert(stiva.top().second);
stiva.pop();
}
bcc[bcc_cnt].insert(stiva.top().first);
bcc[bcc_cnt].insert(stiva.top().second);
stiva.pop();
}
}
else if (disc[c] < disc[nod])
{
stiva.push(make_pair(nod, c));
low[nod] = min(low[nod], disc[c]);
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int u, v;
cin >> u >> v;
la[u].push_back(v);
la[v].push_back(u);
}
dfs(1);
cout << bcc_cnt << '\n';
for (int i = 1; i <= bcc_cnt; ++i)
{
for (auto &x : bcc[i])
cout << x << ' ';
cout << '\n';
}
}
