Cod sursa(job #3230209)

Utilizator Sabin1133Padurariu Sabin Sabin1133 Data 19 mai 2024 22:13:51
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>

#define NMAX 100000


struct Edge {
    int x;
    int y;

    Edge() { }
    Edge(int x, int y)
        : x(x)
        , y(y) { }

    bool operator==(const Edge& other) { return x == other.x && y == other.y; }
    bool operator!=(const Edge& other) { return !(*this == other); }
};


void tarjan(int node, std::vector<int> adj[], std::vector<Edge> &st,
            int &timestamp, int found[], int low_link[],
            std::vector<std::set<int>> &bccs)
{
    ++timestamp;
    found[node] = timestamp;
    low_link[node] = timestamp;


    for (auto neigh : adj[node]) {
        if (found[neigh] == -1) {
            st.push_back({node, neigh});
            tarjan(neigh, adj, st, timestamp, found, low_link, bccs);
            low_link[node] = std::min(low_link[node], low_link[neigh]);

            if (low_link[neigh] >= found[node]) {
                Edge st_edge, first_edge(node, neigh);

                bccs.push_back({});

                do {
                    st_edge = st.back();
                    st.pop_back();
                    bccs.back().insert(st_edge.x);
                    bccs.back().insert(st_edge.y);
                } while (st_edge != first_edge);
            }
        } else {
            low_link[node] = std::min(low_link[node], found[neigh]);
        }
    }
}

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

    int n, m;
    std::vector<int> adj[NMAX];
    int timestamp = 0, found[NMAX], low_link[NMAX];
    std::vector<Edge> st;
    std::vector<std::set<int>> bccs;


    fin >> n >> m;

    for (int v, w, i = 0; i < m; ++i) {
        fin >> v >> w;
        adj[v - 1].push_back(w - 1);
    }


    for (int i = 0; i < n; ++i)
        found[i] = -1;

    for (int i = 0; i < n; ++i)
        if (found[i] == -1)
            tarjan(i, adj, st, timestamp, found, low_link, bccs);


    fout << bccs.size() << '\n';

    for (auto bcc : bccs) {
        for (auto node : bcc)
            fout << node + 1 << ' ';

        fout << '\n';
    }


    fin.close();
    fout.close();

    return 0;
}