Cod sursa(job #1659495)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 22 martie 2016 11:53:20
Problema Nunta Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.26 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <stack>

using namespace std;

ifstream in("drumuri5.in");
ofstream out("drumuri5.out");

void getTsort(const vector<vector<int>> &g, const vector<vector<int>> &tg,
                     vector<int> &tsort, vector<int> &pTsort) {
    int nodes = g.size();
    vector<int> deg(nodes, 0);
    queue<int> q;

    tsort.clear();
    pTsort.assign(nodes, 0);

    for(int i = 0; i < nodes; i++) {
        deg[i] = tg[i].size();
        if(!deg[i]) q.push(i);
    }

    while(!q.empty()) {
        const int cur = q.front();
        q.pop();
        pTsort[cur] = tsort.size();
        tsort.push_back(cur);
        for(const auto nxt : g[cur]) {
            deg[nxt]--;
            if(!deg[nxt]) {
                q.push(nxt);
            }
        }
    }
}

void countAccessible(const vector<int> &tsort, const vector<int> &pTsort,
                            const vector<vector<int>> &g, const vector<vector<int>> &tg,
                            vector<int> &cntAcc) {
    int nodes = g.size();

    for(int i = nodes - 1; i >= 0; i--) {
        const int cur = tsort[i];
        cntAcc[cur]++;
        if(tg[cur].size() == 0) { /// The node is a root.
            continue;
        }
        int maxPos = -1;
        for(const int nxt : tg[cur]) {
            maxPos = max(maxPos, pTsort[nxt]);
        }
        cntAcc[tsort[maxPos]] += cntAcc[cur];
    }
}

void countBothAccessible(const vector<vector<int>> &g, const vector<vector<int>> &tg, vector<int> &countTotal) {
    int nodes = g.size();
    vector<int> pTsort(nodes, 0), tsort;
    vector<int> cntLeft(nodes, 0), cntRight(nodes, 0);

    getTsort(g, tg, tsort, pTsort);
    countAccessible(tsort, pTsort, g, tg, cntRight);



    getTsort(tg, g, tsort, pTsort);
    countAccessible(tsort, pTsort, tg, g, cntLeft);

    for(int i = 0; i < nodes; i++) {
        countTotal[i] = cntLeft[i] + cntRight[i];
    }
}

void dfsScc(const vector<vector<int>> &g, const int &cur, vector<int> &h, vector<int> &lowlink,
            stack<int> &stk, vector<bool> &onStk, vector<vector<int>> &sccList, vector<int> &indexScc) {
    lowlink[cur] = h[cur];
    stk.push(cur);
    onStk[cur] = true;
    for(const auto nxt : g[cur]) {
        if(h[nxt]) {
            if(onStk[nxt]) {
                lowlink[cur] = min(lowlink[cur], h[nxt]);
            }
        }
        else {
            h[nxt] = h[cur] + 1;
            dfsScc(g, nxt, h, lowlink, stk, onStk, sccList, indexScc);
            lowlink[cur] = min(lowlink[cur], lowlink[nxt]);
        }
    }
    if(lowlink[cur] == h[cur]) {
        vector<int> newScc;
        while(stk.top() != cur) {
            int node = stk.top();
            onStk[node] = false;
            newScc.push_back(node);
            indexScc[node] = sccList.size();
            stk.pop();
        }
        onStk[cur] = false;
        newScc.push_back(cur);
        indexScc[cur] = sccList.size();
        stk.pop();

        sccList.push_back(newScc);
    }
}

void getScc(const vector<vector<int>> &g, vector<int> &h, vector<int> &lowlink, vector<vector<int>> &sccList,
            vector<int> &indexScc) {
    stack<int> stk;
    vector<bool> onStk(g.size(), false);

    for(int i = 0; i < g.size(); i++) {
        if(h[i]) continue;
        h[i] = 1;
        dfsScc(g, i, h, lowlink, stk, onStk, sccList, indexScc);
    }
}

void getSccGraph(const vector<vector<int>> &g, const vector<vector<int>> &sccList,  const vector<int>& indexScc,
                 vector<vector<int>> &sccG, vector<vector<int>> &sccGT) {
    unordered_set < long long > edge_hash;
    const long long HASH_CONST = 1000000;

    for(int i = 0; i < g.size(); i++) {
        for(const auto j : g[i]) {
            int indI = indexScc[i], indJ = indexScc[j];
            long long edge_h_val = HASH_CONST * indI + indJ;

            if(indI == indJ) continue;
            if(edge_hash.find(edge_h_val) != edge_hash.end()) continue;

            edge_hash.insert(edge_h_val);
            sccG[indI].push_back(indJ);
            sccGT[indJ].push_back(indI);
        }
    }
}

int main() {
    int n, m;

    in >> n >> m;

    vector<vector<int>> g(n);
    vector<vector<int>> tg(n);

    for(int i = 0, a, b; i < m; i++) {
        in >> a >> b;
        a--; b--;
        g[a].push_back(b);
        tg[b].push_back(a);
    }

    vector<vector<int>> sccList;
    vector<int> h(n, 0);
    vector<int> lowlink(n, 0);
    vector<int> indexScc(n, 0);

    getScc(g, h, lowlink, sccList, indexScc);

    const int sccN = sccList.size();
    vector<vector<int>> sccG(sccN);
    vector<vector<int>> sccGT(sccN);
    vector<int> accessibleTotal(n, 0);
    vector<int> sol;

    getSccGraph(g, sccList, indexScc, sccG, sccGT);
    countBothAccessible(sccG, sccGT, accessibleTotal);

    for(int i = 0; i < sccN; i++) {
        if(accessibleTotal[i] == sccN + 1) {
            for(const auto j : sccList[i]) {
                sol.push_back(j + 1);
            }
        }
    }

    sort(begin(sol), end(sol));
    out << sol.size() << '\n';
    for(const auto i : sol) {
        out << i << ' ';
    }
    out << '\n';

    return 0;
}