Cod sursa(job #1582936)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 28 ianuarie 2016 17:12:48
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

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

const int MAX_N = 100000;

int n, m, biconCount;
vector < int > A[1 + MAX_N];
int H[1 + MAX_N];
int lowLink[1 + MAX_N];
stack < pair < int, int > > S;
vector < int > bicon[1 + MAX_N];

void dfs(int u, int parent) {
    lowLink[u] = H[u];
    for(auto v : A[u]) {
        if(v != parent) {
            if(H[v]) {
                lowLink[u] = min(lowLink[u], H[v]);
            }
            else {
                H[v] = H[u] + 1;
                S.push(make_pair(u, v));
                dfs(v, u);
                if(lowLink[v] >= H[u]) {
                    biconCount++;
                    while(!S.empty() && (S.top().first != u || S.top().second != v)) {
                        bicon[biconCount].push_back(S.top().second);
                        //out << S.top().first << " <-> " << S.top().second << '\n';
                        S.pop();
                    }
                    //out << u << " <-> " << v << '\n';
                    bicon[biconCount].push_back(u);
                    bicon[biconCount].push_back(v);
                    S.pop();
                }
                lowLink[u] = min(lowLink[u], lowLink[v]);
            }
        }
    }
}

void getBicon() {
    for(int i = 1; i <= n; i++) {
        if(H[i] == 0) {
            H[i] = 1;
            dfs(i, 0);
        }
    }
}

int main() {
    int i, u, v;

    in >> n >> m;
    for(i = 1; i <= m; i++) {
        in >> u >> v;
        A[u].push_back(v);
        A[v].push_back(u);
    }

    getBicon();

    out << biconCount << '\n';
    for(i = 1; i <= biconCount; i++) {
        for(auto j : bicon[i]) {
            out << j << ' ';
        }
        out << '\n';
    }

    return 0;
}