Cod sursa(job #2705836)

Utilizator DragosC1Dragos DragosC1 Data 13 februarie 2021 13:25:04
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

int n, m;
vector<int> a[100001], dfn(100001), low(100001);
stack<pair<int, int>> st;
vector<int> C[100001];
int compbiconx;

void read() {
    int x, y, i;
    ifstream f("biconex.in");
    f >> n >> m;
    for (i = 1; i <= m; i++) {
        f >> x >> y;
        a[x].emplace_back(y);
        a[y].emplace_back(x);
    }
    f.close();
}

void inreg(int px, int x) {
    int i;
    vector<int> con; int cpx, cx;
    do {
        cpx = st.top().first, cx = st.top().second;
        st.pop();
        con.emplace_back(cpx); con.emplace_back(cx);
    } while (px != cpx && x != cx);
    sort(con.begin(), con.end());
    C[compbiconx].emplace_back(con[0]);
    for (i = 1; i < con.size(); i++)
        if (con[i] != con[i - 1])
            C[compbiconx].emplace_back(con[i]);
    compbiconx++;
}

void dfs(int x, int px, int nr) {
    int i;
    dfn[x] = low[x] = nr;
    for (i = 0; i < a[x].size(); i++) {
        if (a[x][i] == px)
            continue;
        if (dfn[a[x][i]] == 0) {
            st.push({x, a[x][i]});
            dfs(a[x][i], x, nr + 1);
            low[x] = min(low[x], low[a[x][i]]);
            if (low[a[x][i]] >= dfn[x])
                inreg(x, a[x][i]);
        }
        else low[x] = min(low[x], dfn[a[x][i]]);
    }
}

void solve() {
    int i;
    dfs(1, 0, 1);
}

void output() {
    int i, j;
    ofstream g("biconex.out");
    g << compbiconx << '\n';
    for (i = 0; i < compbiconx; i++) {
        sort(C[i].begin(), C[i].end());
        for (j = 0; j < C[i].size(); j++)
            g << C[i][j] << ' ';
        g << '\n';
    }
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}