Cod sursa(job #3288771)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 24 martie 2025 11:05:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <fstream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;
const int MMAX = 2e5;

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

int n, m, ind_bcc, ind_edges, t;
vector<int> g[NMAX + 1];
vector<int> bcc[NMAX + 1];
pair<int, int> edges[MMAX + 1];
int dfs_time[NMAX + 1];
int low[NMAX + 1];

void GetBCC(pair<int, int> root_edge) {
    ind_bcc++;
    while(root_edge != edges[ind_edges]) {
        bcc[ind_bcc].push_back(edges[ind_edges].first);
        bcc[ind_bcc].push_back(edges[ind_edges].second);
        ind_edges--;
    }
    bcc[ind_bcc].push_back(edges[ind_edges].first);
    bcc[ind_bcc].push_back(edges[ind_edges].second);
    ind_edges--;

    sort(bcc[ind_bcc].begin(), bcc[ind_bcc].end());
    bcc[ind_bcc].erase(unique(bcc[ind_bcc].begin(), bcc[ind_bcc].end()), bcc[ind_bcc].end());
}

void DFS(int node, int dad = 0) {
    dfs_time[node] = low[node] = ++t;
    for(int next_node : g[node]) {
        if(!dfs_time[next_node]) {
            edges[++ind_edges] = {node, next_node};
            DFS(next_node, node);

            low[node] = min(low[node], low[next_node]);
            if(low[next_node] >= dfs_time[node]) {
                GetBCC({node, next_node});
            }
        }
        else if(next_node != dad && dfs_time[node] > dfs_time[next_node]) {
            low[node] = min(low[node], dfs_time[next_node]);
            edges[++ind_edges] = {node, next_node};
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    DFS(1);

    cout << ind_bcc << '\n';
    for(int i = 1; i <= ind_bcc; i++) {
        for(int x : bcc[i]) {
            cout << x << ' ';
        }
        cout << '\n';
    }

    return 0;
}