Cod sursa(job #2928328)

Utilizator AndreiAncutaAndrei Ancuta AndreiAncuta Data 22 octombrie 2022 19:15:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.31 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

using AdjList = vector<vector<int>>;

class Tarjan {
    const int UNVISITED = -1;

    const AdjList &adjList;
    int nodeCount;

    int currentId = 0;
    vector<int> ids;
    vector<int> lowlink;
    vector<bool> isOnStack;
    stack<int> nodeStack;

    vector<vector<int>> components;

    void dfs(int node) {
        ids[node] = lowlink[node] = currentId++;
        isOnStack[node] = true;
        nodeStack.push(node);

        for (int nextNode : adjList[node]) {
            if (ids[nextNode] == UNVISITED) {
                dfs(nextNode);
            }
            if (isOnStack[nextNode]) {
                lowlink[node] = min(lowlink[node], lowlink[nextNode]);
            }
        }

        if (ids[node] == lowlink[node]) {
            components.emplace_back();

            // Pop stack until after the current node
            while (true) {
                auto topNode = nodeStack.top();
                nodeStack.pop();
                isOnStack[topNode] = false;
                // Set component id
                lowlink[topNode] = ids[node];

                components.back().push_back(topNode);

                if (topNode == node) break;
            }
        }
    }

public:
    Tarjan(AdjList &adjList)
        : adjList(adjList)
        , nodeCount(adjList.size())
        , ids(nodeCount, UNVISITED)
        , lowlink(nodeCount)
        , isOnStack(nodeCount, false) {}

    vector<vector<int>> run() {
        for (int node = 1; node < nodeCount; ++node) {
            if (ids[node] == UNVISITED) {
                dfs(node);
            }
        }

        return components;
    }
};

int main() {
    ifstream fin("ctc.in");

    int nodeCount, edgeCount;
    fin >> nodeCount >> edgeCount;

    AdjList adjList(nodeCount + 1);

    // Read edges
    for (int i = 0; i < edgeCount; ++i) {
        int node1, node2;
        fin >> node1 >> node2;
        adjList[node1].push_back(node2);
    }

    Tarjan tarjan(adjList);

    auto components = tarjan.run();

    ofstream fout("ctc.out");

    fout << components.size() << '\n';
    for (const auto &component : components) {
        for (int node : component) {
            fout << node << ' ';
        }
        fout << '\n';
    }

    return 0;
}