Cod sursa(job #2628358)

Utilizator AlexNeaguAlexandru AlexNeagu Data 15 iunie 2020 17:08:09
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
const int N = 100006;
vector < int > E[N];
ifstream in("biconex.in");
ofstream out("biconex.out");
vector < vector < int > > comps;
int tin[N], dp[N], timer = 0;
bool viz[N];
stack < int > s;
void dfs(int node, int pre) {
    s.push(node);
    tin[node] = timer++;
    dp[node] = tin[node];
    viz[node] = 1;
    for (auto it : E[node]) {
        if (it != pre) {
            if (viz[it]) {
                dp[node] = min(dp[node], tin[it]);
            } else {
                dfs(it, node);
                dp[node] = min(dp[node], dp[it]);
                if (dp[it] >= tin[node]) {
                    comps.emplace_back();
                    while(1) {
                        int val = s.top();
                        comps.back().push_back(val);
                        s.pop();
                        if (val == it) break;
                    }
                    comps.back().push_back(node);
                }
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cerr.tie(0);
    cout.tie(0);
    int n, m;
    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        in >> x >> y;
        E[x].push_back(y);
        E[y].push_back(x);
    }
    dfs(1, 0);
    out << comps.size() << '\n';
    for (int i = 0; i < comps.size(); i++) {
        for (auto it : comps[i]) {
            out << it << ' ';
        }
        out << '\n';
    }
    return 0;
}