Cod sursa(job #3195572)

Utilizator tibinyteCozma Tiberiu-Stefan tibinyte Data 21 ianuarie 2024 11:57:58
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <bits/stdc++.h>

#define cin fin
#define cout fout

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> low(n + 1, INT_MAX);
    vector<int> when(n + 1);
    int p = 1;
    stack<pair<int, int>> s;
    vector<vector<pair<int, int>>> biconexe;
    function<void(int)> dfs = [&](int node)
    {
        when[node] = p++;
        for (auto i : g[node])
        {
            if (when[i] == 0)
            {
                s.push({node, i});
                dfs(i);
                if (when[node] <= low[i])
                {
                    biconexe.push_back({});
                    while (true)
                    {
                        pair<int, int> je = s.top();
                        biconexe.back().push_back(je);
                        s.pop();
                        if (je == pair<int, int>{node, i})
                        {
                            break;
                        }
                    }
                }
                low[node] = min(low[node], low[i]);
            }
            else
            {
                low[node] = min(low[node], when[i]);
            }
        }
    };
    dfs(1);
    cout << (int)biconexe.size() << '\n';
    for (auto i : biconexe)
    {
        vector<int> noduri;
        for (auto j : i)
        {
            noduri.push_back(j.first);
            noduri.push_back(j.second);
        }
        sort(noduri.begin(), noduri.end());
        noduri.erase(unique(noduri.begin(), noduri.end()), noduri.end());
        for (auto j : noduri)
        {
            cout << j << ' ';
        }
        cout << '\n';
    }
}