Cod sursa(job #3337302)

Utilizator petru-robuRobu Petru petru-robu Data 27 ianuarie 2026 10:05:49
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m;
vector<vector<int>> adj_list;
vector<int> level, min_level, visited;

stack<pair<int, int>> st;
vector<vector<int>> comp;

void read()
{
    fin >> n >> m;

    adj_list.assign(n + 1, {});
    level.assign(n + 1, 0);
    min_level.assign(n + 1, 0);
    visited.assign(n + 1, 0);

    for (int i = 0; i < m; i++)
    {
        int x, y;
        fin >> x >> y;

        adj_list[x].push_back(y);
        adj_list[y].push_back(x);
    }
}

void getComponent(int x, int y)
{
    if (st.empty())
        return;

    vector<int> nodes;

    auto [topx, topy] = st.top(); 
    st.pop();
    
    nodes.push_back(topx);
    nodes.push_back(topy);

    while (!st.empty() && (topx != x || topy != y))
    {
        topx = st.top().first;
        topy = st.top().second;
        st.pop();
        nodes.push_back(topx);
        nodes.push_back(topy);
    }

    comp.push_back(nodes);
}

void removeDup(vector<int> &v)
{
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

void dfs(int x)
{
    min_level[x] = level[x];
    visited[x] = 1;

    for (auto &next : adj_list[x])
    {
        if (!visited[next])
        {
            st.push({x, next});

            level[next] = level[x] + 1;
            dfs(next);
            min_level[x] = min(min_level[x], min_level[next]);

            if (min_level[next] >= level[x])
            {
                // punct critic
                getComponent(x, next);
            }
        }
        else
        {
            if (level[next] < level[x] - 1)
                min_level[x] = min(min_level[x], level[next]);
        }
    }
}

int main()
{
    read();

    for (int i = 1; i <= n; i++)
        if (!visited[i])
            dfs(i);

    fout << comp.size() << "\n";
    for (auto &c : comp)
    {
        removeDup(c);
        for (auto &x : c)
            fout << x << ' ';
        fout << '\n';
    }

    return 0;
}