Cod sursa(job #2764040)

Utilizator DragosC1Dragos DragosC1 Data 18 iulie 2021 19:48:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <fstream>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m;

vector<int> a[100001];

void read() {
    int i, x, y;
    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);
    }
}

int dfn[100001], low[100001];
stack<pair<int, int>> st;
int art[100001];
vector<int> compbiconex[100001];
int aux[100001];
int nrbiconex, lung;

void count(int px, int x) {
    int cpx, cx;
    lung = 0;
    do {
        cpx = st.top().first, cx = st.top().second;
        st.pop();
        aux[++lung] = cpx, aux[++lung] = cx;
    } while(px != cpx || cx != x);
    sort(aux + 1, aux + lung + 1);
    nrbiconex++;
    compbiconex[nrbiconex].emplace_back(aux[1]);
    for (int i = 2; i <= lung; i++)
        if (aux[i] != aux[i - 1])
            compbiconex[nrbiconex].emplace_back(aux[i]);
}

void dfs(int x, int px, int nr) {
    int i;
    dfn[x] = low[x] = nr;
    for (i = 0; i < a[x].size(); i++) {
        if (px == a[x][i])
            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]) {
                art[x] = 1;
                count(x, a[x][i]);
            }
        }
        else low[x] = min(low[x], dfn[a[x][i]]);
    }
}

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

int main() {
    read();
    dfs(1, 0, 1);
    output();
    return 0;
}