Cod sursa(job #3375056)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 10 noiembrie 2026 03:53:11
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 kb
#include <fstream>
#include <vector>
#include <algorithm>

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

const int NMAX = 100005;
const int MMAX = 200005;

int n, m;
std::vector<int> graph[NMAX];
int order[NMAX], low[NMAX], parent[NMAX], pos[NMAX];
int path[NMAX], depth = 0;
int edgeX[MMAX], edgeY[MMAX], top = 0;
int mark[NMAX];
int timer = 0;
std::vector<std::vector<int>> components;

void popComponent(int x, int y) {
    std::vector<int> component;
    int id = components.size() + 1;
    int a, b;
    do {
        top--;
        a = edgeX[top];
        b = edgeY[top];
        if (mark[a] != id) {
            mark[a] = id;
            component.push_back(a);
        }
        if (mark[b] != id) {
            mark[b] = id;
            component.push_back(b);
        }
    } while (a != x || b != y);
    components.push_back(component);
}

void dfs(int start) {
    order[start] = low[start] = ++timer;
    parent[start] = 0;
    path[depth++] = start;

    while (depth > 0) {
        int node = path[depth - 1];

        if (pos[node] == (int)graph[node].size()) {
            depth--;
            if (depth > 0) {
                int up = path[depth - 1];
                low[up] = std::min(low[up], low[node]);
                if (low[node] >= order[up])
                    popComponent(up, node);
            }
            continue;
        }

        int next = graph[node][pos[node]++];
        if (next == parent[node])
            continue;

        if (!order[next]) {
            edgeX[top] = node;
            edgeY[top] = next;
            top++;
            order[next] = low[next] = ++timer;
            parent[next] = node;
            path[depth++] = next;
        } else if (order[next] < order[node]) {
            edgeX[top] = node;
            edgeY[top] = next;
            top++;
            low[node] = std::min(low[node], order[next]);
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

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

    fout << components.size() << '\n';
    for (auto &component : components) {
        for (int x : component)
            fout << x << ' ';
        fout << '\n';
    }
    return 0;
}