Cod sursa(job #2668523)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 4 noiembrie 2020 23:29:27
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>

using namespace std;

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

vector < int > id, low_id;
vector < vector < int > > G, Components;
stack < pair < int , int > > S;

inline void min_self(int& a, int b) {
    a = min(a, b);
}

void BC(int u, int v) {
    vector < int > new_c;
    int x, y;
    do {
        x = S.top().first, y = S.top().second;
        S.pop();
        new_c.emplace_back(x), new_c.emplace_back(y);
    } while(x != u || y != v);
    Components.emplace_back(new_c);
}

void DFS(int node, int parent, int val) {
    id[node] = low_id[node] = val;
    for(int vec : G[node]) {
        if(vec == parent)
            continue;
        if(id[vec] == -1) {
            S.emplace(node, vec);
            DFS(vec, node, val + 1);
            min_self(low_id[node], low_id[vec]);
            if(low_id[vec] >= id[node])
                BC(node, vec);
        }
        else
            min_self(low_id[node], id[vec]);
    }
}

int main() {
    int N, M;
    fin >> N >> M;
    G.resize(N + 1), id.assign(N + 1, -1), low_id.resize(N + 1);
    while(M--) {
        int u, v;
        fin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    DFS(1, 0, 0);
    fout << Components.size() << '\n';
    for(auto C : Components) {
        sort(C.begin(), C.end());
        C.erase(unique(C.begin(), C.end()), C.end());
        for(int node : C)
            fout << node << ' ';
        fout << '\n';
    }
}