Cod sursa(job #3374238)

Utilizator AnlegliftIvanus Victor Gabriel Anleglift Data 8 noiembrie 2026 21:08:02
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

/*
 * 1. Folosește o parcurgere DFS, menținând timpul de descoperire (`node_index`) și cel mai mic nod accesibil (`low`) pentru fiecare nod.
 * 2. Pune fiecare muchie parcursă (nod curent, vecin) într-o stivă globală.
 * 3. Dacă din vecin se poate ajunge doar la noduri descoperite după sau în același timp cu nodul curent (`low[neighbour] >= node_index[node]`), înseamnă că s-a găsit o componentă biconexă.
 * 4. Extrage muchiile de pe stivă până ajunge la muchia (nod curent, vecin), adăugând nodurile extrase într-o listă.
 * 5. Sortează nodurile extrase, elimină duplicatele și salvează componenta finală.
 *
 * Complexitate: Timp O(N + M), Spațiu O(N + M).
 */

using namespace std;

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

const int MAXN = 100005;
vector<int> graph[MAXN];
int node_index[MAXN], low[MAXN], global_index;

stack<pair<int, int>> edge_stack;
vector<vector<int>> biconex;

void DFS(int node, int parent = 0)
{
    node_index[node] = low[node] = ++global_index;

    for (int neighbour : graph[node])
    {
        if (neighbour == parent)
            continue;

        if (node_index[neighbour] != 0)
        {
            low[node] = min(low[node], node_index[neighbour]);
            if (node_index[neighbour] < node_index[node])
                edge_stack.push({node, neighbour});
        }
        else
        {
            edge_stack.push({node, neighbour});
            DFS(neighbour, node);

            low[node] = min(low[node], low[neighbour]);
            if (low[neighbour] >= node_index[node])
            {
                vector<int> comp_curenta;

                while (true)
                {
                    auto edge = edge_stack.top();
                    edge_stack.pop();

                    comp_curenta.push_back(edge.first);
                    comp_curenta.push_back(edge.second);

                    if (edge.first == node && edge.second == neighbour)
                        break;
                }

                sort(comp_curenta.begin(), comp_curenta.end());
                comp_curenta.erase(unique(comp_curenta.begin(), comp_curenta.end()), comp_curenta.end());

                biconex.push_back(comp_curenta);
            }
        }
    }
}

int main()
{
    int n, m;
    fin >> n >> m;

    for (int i = 0; i < m; ++i)
    {
        int a, b;
        fin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for (int i = 1; i <= n; ++i)
        if (node_index[i] == 0)
            DFS(i);

    fout << biconex.size() << "\n";
    for (const auto &component : biconex)
    {
        for (int x : component)
        {
            fout << x << " ";
        }
        fout << "\n";
    }

    return 0;
}