Cod sursa(job #3375104)

Utilizator 1ionutAvatamanitei Ionut Andrei 1ionut Data 10 noiembrie 2026 12:31:27
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>

const int MAXN = 100005;

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

std::vector<std::pair<int, int>> G[MAXN];
std::vector<std::pair<int, int>> st;
std::vector<std::vector<int>> comp;

int tin[MAXN], low[MAXN], timer = 0;
int marc[MAXN], nrComp = 0;

void componenta(int u, int v) {
    nrComp++;
    std::vector<int> c;

    while (!st.empty()) {
        int x = st.back().first;
        int y = st.back().second;
        st.pop_back();

        if (marc[x] != nrComp) {
            marc[x] = nrComp;
            c.push_back(x);
        }

        if (marc[y] != nrComp) {
            marc[y] = nrComp;
            c.push_back(y);
        }

        if (x == u && y == v)
            break;
    }

    comp.push_back(c);
}

void dfs(int u, int muchieParinte) {
    tin[u] = low[u] = ++timer;

    for (auto e : G[u]) {
        int v = e.first;
        int id = e.second;

        if (id == muchieParinte)
            continue;

        if (tin[v] == 0) {
            st.push_back({ u, v });

            dfs(v, id);

            low[u] = std::min(low[u], low[v]);

            if (low[v] >= tin[u])
                componenta(u, v);
        }
        else if (tin[v] < tin[u]) {
            st.push_back({ u, v });
            low[u] = std::min(low[u], tin[v]);
        }
    }
}

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

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

        G[x].push_back({ y, i });
        G[y].push_back({ x, i });
    }

    for (int i = 1; i <= n; i++)
        if (tin[i] == 0)
            dfs(i, 0);

    fout << comp.size() << '\n';

    for (const auto& c : comp) {
        for (int x : c)
            fout << x << ' ';
        fout << '\n';
    }

    return 0;
}