Участник:Kachanov vv/CAPCITY

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/CAPCITY/

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int maxValue = 100007;
 
class Solution {
public:
    void init() {
        cin >> N >> M;
        for (int i = 0; i < M; i++) {
            int a, b;
            cin >> a >> b;
            graph[a].push_back(b);
            reverseGraph[b].push_back(a);
        }
    }
 
    void process() {
        dfs();
        for (int i = 1; i <= N; i++) {
            for (int j : reverseGraph[i]) {
                if (componentID[1][i] != componentID[1][j]) {
                    degree[componentID[1][j]]++;
                }
            }
        }
        separated = 0;
        for (int i = 1; i <= countStrict; i++) {
            if (!degree[i]) {
                separated++;
            }
        }
    }
 
    void dump() {
        if (separated > 1) {
            cout << "0" << endl;
        } else {
            vector<int> output;
            for (int i = 1; i <= N; i++) {
                if (!degree[componentID[1][i]]) {
                    output.push_back(i);
                }
            }
            cout << (int) output.size();
            auto join = [sep = '\n'](int x) mutable {
                cout << sep << x;
                sep = ' ';
            };
            std::for_each(output.begin(), output.end(), join);
            cout << endl;
        }
    }
 
    void dfs() {
        for (int i = 1; i <= N; i++) {
            if (!visited[0][i]) {
                countReverse++;
                dfsReverse(i);
            }
        }
        reverse(orders.begin(), orders.end());
        for (int i : orders) {
            if (!visited[1][i]) {
                countStrict++;
                dfsStrict(i);
            }
        }
    }
 
    void dfsReverse(int node) {
        visited[0][node] = true;
        componentID[0][node] = countReverse;
        for (int i : reverseGraph[node]) {
            if (!visited[0][i]) {
                dfsReverse(i);
            }
        }
        orders.push_back(node);
    }
 
    void dfsStrict(int node) {
        visited[1][node] = true;
        componentID[1][node] = countStrict;
        for (int i : graph[node]) {
            if (!visited[1][i]) {
                dfsStrict(i);
            }
        }
    }
 
    void solve() {
        init();
        process();
        dump();
    }
 
private:
    int N, M;
    int countStrict, countReverse;
    int componentID[2][maxValue];
    int degree[maxValue];
    bool visited[2][maxValue];
    int separated = 0;
    vector<int> graph[maxValue];
    vector<int> reverseGraph[maxValue];
    vector<int> orders;
 
};
 
int main() {
    Solution solution;
    solution.solve();
    return 0;
}