Cod sursa(job #2251020)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 1 octombrie 2018 00:15:57
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.53 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <assert.h>
#include <queue>
#include <functional>


using LL = long long;
using ULL = int long long;

const std::string _problemName = "ctc";

namespace std {
    std::ifstream fin(_problemName + ".in");
    std::ofstream fout(_problemName + ".out");
}

#define USE_FILES

#ifdef USE_FILES
#define cin fin
#define cout fout
#endif

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

class TarjanSccs {

public:

    std::vector< std::vector<int> >&& computeSccs(const graph_t& graph) {
        init(graph);
        buildSccs();
        return std::move(_sccs);
    }

private:

    const int UNVISITED_INDEX = 0;
    const int FIRST_INDEX = 1;

    void init(const graph_t& graph) {
        _graph = &graph;

        _inStack.resize(graph.size());
        fill(_inStack, false);

        _index.resize(graph.size());
        fill(_index, UNVISITED_INDEX);

        _lowestLink.resize(graph.size());
        fill(_lowestLink, 0);

        clearStack();
        _sccs.clear();

        _globalIndex = 1;
    }

    template <typename Container, typename Value>
    void fill(Container c, Value value) {
        std::fill(std::begin(c), std::end(c), value);
    }

    void buildSccs() {
        for (int node = 0; node < graph().size(); ++node) {
            if (_index[node] == UNVISITED_INDEX) {
                dfs(node);
            }
        }
    }

    void dfs(int node) {
        _index[node] = _globalIndex++;
        _lowestLink[node] = _index[node];

        pushToStack(node);

        for (int neighbour : graph()[node]) {
            if (_index[neighbour] == UNVISITED_INDEX) {
                dfs(neighbour);
                _lowestLink[node] = std::min(_lowestLink[node], _lowestLink[neighbour]);
            }
            else if (_inStack[neighbour]) {
                _lowestLink[node] = std::min(_lowestLink[node], _index[neighbour]);
            }
        }

        if (_index[node] == _lowestLink[node]) {
            buildScc(node);
        }
    }

    void buildScc(int node) {
        _sccs.emplace_back();

        std::vector<int>& scc = _sccs.back();

        do {
            scc.push_back(popFromStack());
        } while (scc.back() != node);
    }

    void pushToStack(int node) {
        _stack.push(node);
        _inStack[node] = true;
    }

    void clearStack() {
        while (!_stack.empty()) {
            _stack.pop();
        }
    }

    int popFromStack() {
        int node = _stack.top();
        _stack.pop();
        _inStack[node] = false;
        return node;
    }

    const graph_t& graph() {
        return *_graph;
    }

    int _globalIndex;
    std::vector< std::vector<int> > _sccs;
    std::vector<int> _index;
    std::vector<int> _lowestLink;
    std::vector<bool> _inStack;
    std::stack<int> _stack;
    const graph_t* _graph;
};

int main() {

    int n, m;
    std::cin >> n >> m;
    graph_t graph(n);

    while (m--) {
        int x, y;
        std::cin >> x >> y;
        x--, y--;

        graph[x].push_back(y);
    }

    std::vector< std::vector<int> > sccs = TarjanSccs().computeSccs(graph);

    std::cout << sccs.size() << '\n';
    for (const auto& scc : sccs) {
        for (int node : scc) {
            std::cout << node + 1 << ' ';
        }
        std::cout << '\n';
    }

    return 0;
}