Cod sursa(job #1420482)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 18 aprilie 2015 16:14:32
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
#include <fstream>
#include <vector>
#include <stack>
#include <unordered_set>

using Graph = std::vector<std::vector<int>>;


const int NMAX = 100005;
Graph G(NMAX);
std::vector<int> indexes(NMAX, -1);
std::vector<int> lowlinks(NMAX);

void tarjan(int node,
            int parent,
            std::stack<std::pair<int, int>> &st,
            std::vector<std::unordered_set<int>> &comps,
            int &currIndex)
{
    indexes[node] = lowlinks[node] = currIndex;

    for (auto &neigh : G[node]) {
        // Ignorăm vecinul nodului curent care este de fapt tatăl său în
        // arborele DFS, deoarece de acolo am ajuns aici oricum.
        if (neigh == parent)
            continue;

        // Dacă nu am vizitat acest nod încă.
        if (indexes[neigh] == -1) {
            // Îl punem în stivă alături de tatăl său și continuăm recursiv.
            st.emplace(node, neigh);
            tarjan(neigh, node, st, comps, ++currIndex);

            // Updatăm lowlinkul nodului curent. În acest moment am vizitat
            // întreaga ramură a arborelui care pornește din vecinul curent al
            // nodului.
            lowlinks[node] = std::min(lowlinks[node], lowlinks[neigh]);

            if (lowlinks[neigh] >= indexes[node]) {
                std::unordered_set<int> comp;
                int child, parent;

                do {
                    comp.emplace((parent = st.top().first));
                    comp.emplace((child = st.top().second));

                    st.pop();
                } while (parent != node || child != neigh);

                comps.emplace_back(comp);
            }
        } else {
            lowlinks[node] = std::min(lowlinks[node], lowlinks[neigh]);
        }
    }
}

int main()
{
    std::ifstream fin{"biconex.in"};
    std::ofstream fout{"biconex.out"};

    int N, M;
    fin >> N >> M;

    for (auto i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;

        G[x - 1].emplace_back(y - 1);
        G[y - 1].emplace_back(x - 1);
    }

    std::vector<std::unordered_set<int>> comps;
    std::stack<std::pair<int, int>> st;
    auto currIndex = -1;

    for (auto i = 0; i < N; ++i)
        if (indexes[i] == -1)
            tarjan(i, -1, st, comps, ++currIndex);

    fout << comps.size() << '\n';
    for (auto &comp : comps) {
        for (auto &e : comp)
            fout << e + 1 << ' ';
        fout << '\n';
    }

    return 0;
}