Cod sursa(job #1639712)

Utilizator cautionPopescu Teodor caution Data 8 martie 2016 13:38:22
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <utility>

constexpr int kMaxN = 100000;

int n, m;
std::vector<int> edges[kMaxN+1];
int discovery_time[kMaxN+1], low[kMaxN+1];
std::vector<std::vector<int> > biconex_componenets;
std::stack<int> S;
int static_time;

void dfs(int x)
{
    ++static_time;
    discovery_time[x] = static_time;
    low[x] = static_time;
    S.push(x);
    for(auto y : edges[x]) {
        if(discovery_time[y] == 0) {
            dfs(y);
            if(discovery_time[x] <= low[y]) {
                std::vector<int> temp;
                while(S.top() != x) {
                    temp.push_back(S.top());
                    S.pop();
                }
                temp.push_back(x);
                biconex_componenets.push_back(std::move(temp));
            }
            else low[x] = std::min(low[x], low[y]);
        }
        else { // a back edge
            low[x] = std::min(low[x], discovery_time[y]);
        }
    }
}

int main()
{
    std::ifstream in("biconex.in");
    std::ofstream out("biconex.out");
    in>>n>>m;
    for(int x, y, i = 1; i <= m; ++i) {
        in>>x>>y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i) {
        if(discovery_time[i] == 0) dfs(i);
    }
    out<<biconex_componenets.size()<<'\n';
    for(auto& bc : biconex_componenets) {
        for(auto x : bc) out<<x<<' ';
        out<<'\n';
    }
    return 0;
}