Cod sursa(job #2590115)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 27 martie 2020 15:45:32
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.99 kb
#include <bits/stdc++.h>

int N, M;
std::vector <std::vector <int>> graph;
inline void addEdge(int u, int v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
}

#define DETECT_ART  false
#define DETECT_CRIT false

class BiconexCalculator {
public:
    BiconexCalculator (std::vector <std::vector <int>> &graph) { calculate(graph); }
    void calculate(std::vector <std::vector <int>> &graph) {
        _time = 0;
        nart  = 0;
        N = graph.size();
        low .resize(graph.size(), 0);
        disc.resize(graph.size(), 0);
        if (DETECT_ART) art.resize (graph.size(), false);
        for (int i=0; i<graph.size(); ++i)
            if (!disc[i]) root = i, DFS(graph, i);
    }

    int getSize() { return components.size(); }
    std::vector <std::vector <int>> getComponents() { return components; }

    int  getArticulationSize()            { return nart; }
    bool isArticulationPoint(int vertex) { return art[vertex]; }
    std::vector <int> getArticulationPoints() {
        std::vector <int> ans;
        for (int i=0; i<N; ++i) if (art[i]) ans.push_back(i);
        return ans;
    }

    int getCriticalSize() { return crit.size(); }
    std::vector <std::pair <int, int>> getCriticalEdges() { return crit; }

    std::vector <std::vector <int>> getBCCGraph(std::vector <std::vector <int>>& graph) {
        std::vector <std::vector <int>> BCCGraph;
        BCCGraph.resize(components.size());
        std::vector <bool> seen(components.size(), false);
        for (int i=0; i<components.size(); ++i) {
            for (auto &u:components[i]) {
                for (auto &it:graph[u])
                    if (comp[it] != i && !seen[comp[it]])
                        BCCGraph[i].push_back(comp[it]), seen[comp[it]] = true;
            }
            for (auto &it:BCCGraph[i]) seen[it] = false;
        }   return BCCGraph;
    }

private:
    void DFS(std::vector <std::vector <int>> &graph, int vertex, int parent = 0) {
        disc[vertex] = low[vertex] = ++_time;
        int children = 0;
        for (auto &it:graph[vertex]) {
            if (it == parent) continue;
            if (!disc[it]) {
                ++ children;
                stack.push({vertex, it});
                DFS(graph, it, vertex);
                low[vertex] = std::min(low[vertex], low[it]);
                if (low[it] >= disc[vertex]) {
                    if (vertex != root)         addArticulationPoint(vertex);
                    if (low[it] > disc[vertex]) addCriticalEdge(it, vertex);
                    addComponent(vertex);
                }
            }   else low[vertex] = std::min(low[vertex], disc[it]);
        }
        if (vertex == root && children > 1) addArticulationPoint(vertex);
    }

    void addArticulationPoint(int vertex)   { if (DETECT_ART) nart += !art[vertex], art[vertex] = true; }
    void addCriticalEdge     (int u, int v) { if (DETECT_CRIT) crit.push_back({u, v}); }
    void addComponent        (int vertex)   {
        components.push_back(std::vector <int> ());
        while (stack.top().first != vertex) {
            components.back().push_back(stack.top().second);
            stack.pop();
        }   components.back().push_back(stack.top().second); components.back().push_back(stack.top().first);
        stack.pop();
    }

    int _time, root;
    int N, nart;
    std::vector <int> low, disc, comp;
    std::vector <std::vector <int>> components;
    std::vector <std::pair <int, int>> crit;
    std::vector <bool> art;
    std::stack  <std::pair <int, int>> stack;
};

std::ifstream input ("biconex.in");
std::ofstream output("biconex.out");

int main()
{
    input >> N >> M;
    graph.resize(N, std::vector <int>());
    for (int i=0, u, v; i<M; ++i) input >> u >> v, addEdge(u-1, v-1);

    BiconexCalculator calc(graph);
    output << calc.getSize() << '\n';
    for (auto &it:calc.getComponents()) {
        for (auto &it2:it)  output << it2+1 << ' ';
        output << '\n';
    }

    return 0;
}