Cod sursa(job #1590053)

Utilizator lorundlorund lorund Data 4 februarie 2016 17:54:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 5.02 kb
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <stack>
#include <queue>

template <class T>
class Graph{
public:
    std::vector<std::vector<T>> graph;
    unsigned nrNodes;
    unsigned nrEdges;
    std::vector<T> &operator[](unsigned node) {
        return graph[node];
    }
    bool Create(unsigned nrNodes) {
        graph.resize(nrNodes);
        this->nrNodes = nrNodes;
        return true;
    }
    bool TopologicalSort(std::vector<unsigned> &result) {
        std::stack<std::pair<unsigned, unsigned>> st;
        std::vector<bool> visited(graph.size());
        unsigned tr;

        for (tr = 0; tr<nrNodes; ++tr) {
            if (!visited[tr]) {
                st.push(std::make_pair(tr, 0));
                visited[tr] = true;
                while (st.size()) {
                    unsigned gr = st.top().first; // current node
                    unsigned &br = st.top().second; // adjacency list index

                    if (br < graph[gr].size()) {
                        if (!visited[graph[gr][br]]) {
                            visited[graph[gr][br]] = true;
                            st.push(std::make_pair(graph[gr][br], 0));
                        }
                        ++br;
                    }
                    else {
                        st.pop();
                        result.push_back(gr);
                    }
                }
            }
        }
        std::reverse(result.begin(), result.end());

        return true;
    }
    bool ConnectedComponents(std::vector<std::vector<unsigned>> &components) {
        std::vector<unsigned> parent;
        unsigned parentFrom, parentTo, index;
        std::unordered_map<unsigned, unsigned> componentIndex;

        for (unsigned i = 0; i<nrNodes; ++i) {
            parent.push_back(i);
        }

        for (unsigned i = 0; i<nrNodes; ++i) {
            for (unsigned j = 0; j<graph[i].size(); ++j) {
                parentFrom = i;
                parentTo = graph[i][j];

                while (parent[parentFrom] != parentFrom) {
                    parentFrom = (parent[parentFrom] = parent[parent[parentFrom]]);
                }
                while (parent[parentTo] != parentTo) {
                    parentTo = (parent[parentTo] = parent[parent[parentTo]]);
                }
                if (parentFrom != parentTo) {
                    parent[parentFrom] = parentTo;
                }
            }
        }

        for (unsigned i = 0; i<nrNodes; ++i) {
            parentFrom = parent[i];
            while (parent[parentFrom] != parentFrom) {
                parentFrom = (parent[parentFrom] = parent[parent[parentFrom]]);
            }
            if (!componentIndex.count(parentFrom)) {
                unsigned index = componentIndex.size();
                componentIndex[parentFrom] = index;
                components.push_back(std::vector<unsigned>());
            }
            index = componentIndex[parentFrom];
            components[index].push_back(i);
        }
        return true;
    }
    bool StrongComponents(std::vector<std::vector<unsigned>> &components) {
        std::vector<unsigned> tsorted;
        std::vector<std::vector<unsigned>> tgraph(graph.size());;
        std::vector<bool> visited(graph.size());
        unsigned tr, gr, br;

        TopologicalSort(tsorted);
        for (tr = 0; tr<graph.size(); ++tr) {
            for (gr = 0; gr<graph[tr].size(); ++gr) {
                tgraph[graph[tr][gr]].push_back(tr);
            }
        }
        for (tr = 0; tr<tsorted.size(); ++tr) {
            if (!visited[tsorted[tr]]) {
                components.push_back(std::vector<unsigned>());
                std::vector<unsigned> &component = components.back();

                component.push_back(tsorted[tr]);
                visited[tsorted[tr]] = true;
                for (gr = 0; gr<component.size(); ++gr) {
                    for (br = 0; br<tgraph[component[gr]].size(); ++br) {
                        if (!visited[tgraph[component[gr]][br]]) {
                            visited[tgraph[component[gr]][br]] = true;
                            component.push_back(tgraph[component[gr]][br]);
                        }
                    }
                }
            }
        }

        return true;
    }
};

int main(int argc, char *argv[])
{
    int n, m;
    Graph<int> g;
    std::vector<std::vector<unsigned>> components;

    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    scanf("%d %d", &n, &m);
    g.Create(n);
    for (int i=0; i<m; ++i){
        int x, y;

        scanf("%d %d", &x, &y);
        g[x-1].push_back(y-1);
    }
    g.StrongComponents(components);
    printf("%d\n", components.size());
    for (int i=0; i<components.size(); ++i){
        for (int j=0; j<components[i].size(); ++j){
            printf("%d ", components[i][j]+1);
        }
        puts("");
    }

    return 0;
}