Cod sursa(job #3125439)

Utilizator Bogdy_PPrunescu Bogdan Bogdy_P Data 3 mai 2023 10:23:38
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> adj[100005];
int n, m;

int timestamp = 0;
int found[100005];
int low_link[100005];

vector<vector<int>> bcc;
vector<int> scc;

stack<pair<int, int>> sc;

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

void DFS(int node) {

    found[node] = ++timestamp;
    low_link[node] = timestamp;

    for (auto neigh : adj[node]) {
        if (found[neigh] == -1) {

            sc.push({node, neigh});

            DFS(neigh);

            low_link[node] = min(low_link[neigh], low_link[node]);

            if (low_link[neigh] >= found[node]) {

                vector<int> current_bcc;

                pair<int, int> current_edge = {node, neigh};

                pair<int, int> stack_edge = {-1, -1};

                while (stack_edge != current_edge) {
                    stack_edge = sc.top();
                    sc.pop();

                    current_bcc.push_back(stack_edge.first);
                    current_bcc.push_back(stack_edge.second);
                }

                sort(current_bcc.begin(), current_bcc.end());
                auto it = unique(current_bcc.begin(), current_bcc.end());
                current_bcc.erase(it, current_bcc.end());

                bcc.push_back(current_bcc);
            }
        } else {
            low_link[node] = min(found[neigh], low_link[node]);
        }
    }
}

int main() {
    in >> n >> m;
    for (int i = 1, x, y; i <= m; i++) {
        in >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        low_link[i] = 1e9;
        found[i] = -1;
    }

    for (int i = 1; i <= n; i++) {
            if (found[i] == -1) {
                DFS(i);
            }
        }

    out << bcc.size() << '\n';
    for (auto x : bcc) {
        for (auto node : x) {
            out << node << ' ';
        }
        out << '\n';
    }
}