Cod sursa(job #2159533)

Utilizator OpportunityVlad Negura Opportunity Data 10 martie 2018 23:47:07
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.4 kb
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(false);cout.precision(30);cout.tie(0);cin.tie(0);
#define ll long long
#define ld long double
#define rep(i, a, b) for(__typeof(b)i=(a)-((a)>(b));i!=(b)-((a)>(b));i+=1-2*((a)>(b)))
#define whilet() ll t;cin>>t;while(t--)
#define all(c) (c).begin(), (c).end()
template <class TCost>
class Graph {
public:
    struct Edge {
        long from, to;
        TCost cost;
        Edge(long _from, long _to, TCost _cost): from(_from), to(_to), cost(_cost) {};
    };
    long size;
    bool zeroIndexed;
    vector<Edge> edges;
    vector<vector<pair<long, TCost>>> adjacencyList;
    Graph() {};
    Graph(long _size, bool _zeroIndexed = true) {
        zeroIndexed = _zeroIndexed;
        if (!zeroIndexed) _size++;
        size = _size;
        adjacencyList.resize(_size);
    };
    ~Graph() = default;
};
template <class TCost>
class DirectedGraph : public Graph<TCost> {
public:
    DirectedGraph() {};
    DirectedGraph(long _size, bool _zeroIndexed): Graph<TCost>(_size, _zeroIndexed) {};
    DirectedGraph(long _size): Graph<TCost>(_size) {};
    void addEdge(long from, long to, TCost cost = 0) {
        this->edges.push_back({from, to, cost});
        this->adjacencyList[from].push_back({to, cost});
    }
    void printEdges() {
        for (auto edge: this->edges) {
            cout << edge.from << ' ' << edge.to << endl;
        }
    }
};

template <class TCost>
class SCC {
public:
    static void TarjanRecursion(
            long v,
            long &indexCount,
            vector<long> &index,
            vector<long> &low,
            stack<long> &S,
            DirectedGraph<TCost> &graph,
            vector<bool> &onStack,
            vector<vector<long>> &components
    ) {
        index[v] = indexCount;
        low[v] = indexCount;
        indexCount++;
        S.push(v);
        onStack[v] = true;
        for (auto edge: graph.adjacencyList[v]) {
            long w = edge.first;
            if (!index[w]) {
                TarjanRecursion(w, indexCount, index, low, S, graph, onStack, components);
                low[v] = min(low[v], low[w]);
            } else if (onStack[w]) {
                low[v] = min(low[v], index[w]);
            }
        }

        if (low[v] == index[v]) {
            vector<long> component;
            long w;
            do {
                w = S.top();
                S.pop();
                onStack[w] = false;
                component.push_back(w);
            } while (w != v);
            components.push_back(component);
        }
    }
    static vector<vector<long>> Tarjan(DirectedGraph<TCost> graph) {
        long indexCount = 1;
        vector<long> index(graph.size), low(graph.size);
        vector<bool> onStack(graph.size);
        stack<long> S;
        vector<vector<long>> components;
        for (long i=(graph.zeroIndexed?0:1); i<graph.size; i++) {
            if (!index[i]) {
                TarjanRecursion(i, indexCount, index, low, S, graph, onStack, components);
            }
        }

        return components;
    }
};

ifstream fi("ctc.in");
ofstream fo("ctc.out");
ll n,m;

int main() {_
    fi >> n >> m;
    DirectedGraph<ll> g(n, false);
    rep(i,0,m) {
        ll x,y;
        fi >> x >> y;
        g.addEdge(x,y);
    }

    auto rs = SCC<ll>::Tarjan(g);
    fo << rs.size() << endl;
    for (auto x:rs) {
        for (auto y:x) fo << y << ' ';
        fo << "\n";
    }

    return 0;
}