Cod sursa(job #1947810)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 31 martie 2017 13:34:26
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
/**
  *  Worg
  */
#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>

using std::pair;
using std::stack;
using std::vector;
FILE *fin = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);

const int kMaxN = 1 + 100000;

/*-------- Input data --------*/
int N, M;
vector<int > graph[kMaxN];
/*-------- Biconnected components data --------*/
int level[kMaxN], dp[kMaxN];

stack<pair<int, int > > edge_stack;

vector<int > comp;
vector<vector<int > > bc_comps;
/*-------- --------*/

void ReadInput() {
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++) {
        int u, v; scanf("%d%d", &u, &v);
        graph[u].push_back(v); graph[v].push_back(u);
    }
}

void AddComponent(const pair<int, int > stop) {
    pair<int, int > edge;
    do {
        edge = edge_stack.top(); edge_stack.pop();
        comp.push_back(edge.first); comp.push_back(edge.second);
    }while(edge != stop);

    std::sort(comp.begin(), comp.end());
    comp.erase(std::unique(comp.begin(), comp.end()), comp.end());

    bc_comps.push_back(comp); comp.clear();
}

void DFS(int node = 1, int father = 0) {
    dp[node] = level[node];
    for(int nxt : graph[node]) {
        if(!level[nxt]) {
            edge_stack.push(std::make_pair(node, nxt));
            level[nxt] = level[node] + 1;
            DFS(nxt, node);

            if(dp[nxt] >= level[node]) {
                AddComponent(std::make_pair(node, nxt));
            }
        }
    }

    bool ok_father = false;
    for(int nxt : graph[node]) {
        if(nxt == father && !ok_father) {
            ok_father = true;
        } else {
            dp[node] = std::min(dp[node], dp[nxt]);
        }
    }
}

void WriteOutput() {
    printf("%d\n", (int)bc_comps.size());
    for(auto bc_comp : bc_comps) {
        for(auto node : bc_comp) {
            printf("%d ", node);
        }
        printf("\n");
    }
}

int main() {
    ReadInput();
    level[1] = 1; DFS();
    WriteOutput();
    return 0;
}