Cod sursa(job #2682259)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 8 decembrie 2020 12:08:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define fi first
#define se second
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair< int , int > PII;

int n, m, cnt;
vector < int > V[100100], R[100100];
bitset < 100100 > B;

int dad[100100], d[100100], low[100100];
stack < PII > S;

void get_component(PII m) {
    ++cnt;

    while (S.top() != m) {
        auto e = S.top();
        S.pop();

        R[cnt].push_back(e.second);
    }

    auto e = S.top();
    S.pop();

    R[cnt].push_back(e.first);
    R[cnt].push_back(e.second);
}

void find_biconex(int x, int parent, int depth) {
    B[x] = 1;
    d[x] = depth;
    low[x] = depth;

    for (auto it : V[x]) {
        if (!B[it]) {
            S.push({x, it});
            find_biconex(it, x, depth + 1);
            low[x] = min(low[x], low[it]);

            if (parent == -1 && V[x].size() > 1) {
                get_component({x, it});
            } else if (low[it] >= depth) {
                get_component({x, it});
            }
        } else if (it != parent) {
            low[x] = min(low[x], d[it]);
        }
    }
}

int main(){
    ifstream cin("biconex.in");
    ofstream cout("biconex.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 1, x, y; i <= m; i++) {
        cin >> x >> y;

        V[x].push_back(y);
        V[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        if (!B[i]) {
            find_biconex(i, -1, 1);
        }
    }

    cout << cnt << "\n";
    for (int i = 1; i <= cnt; i++) {
        for (auto it : R[i]) {
            cout << it << " ";
        }

        cout << "\n";
    }
    
    return 0;
}