spoj_capcity_kosaraju.cpp

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Capcity {
private:
  void dfs(vector<vector<int>>& graph, int root, vector<bool>& visited, vector<int>& cache) {
    if (visited[root]) {
      return;
    }
    visited[root] = true;
    for (int x : graph[root]) {
      dfs(graph, x, visited, cache);
    }
    cache.push_back(root);
  }
public:
  vector<int> kosaraju(vector<vector<int>>& graph, vector<vector<int>>& graphT) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<int> dfsCache;
    for (int i = 0; i < n; ++i) {
      dfs(graph, i, visited, dfsCache);
    }
    fill(visited.begin(), visited.end(), false);

    vector<vector<int>> sccNodes;

    for (int i = n - 1; i >= 0; --i) {
      if (visited[dfsCache[i]]) {
        continue;
      }
      vector<int> nodes;
      dfs(graphT, dfsCache[i], visited, nodes);
      sccNodes.push_back(nodes);
    }

    vector<int> sccMap(n);

    int sccN = sccNodes.size();
    vector<int> indegrees(sccN, 0);

    for (int i = 0; i < sccN; ++i) {
      for (int x : sccNodes[i]) {
        sccMap[x] = i;
      }
    }

    vector<unordered_set<int>> sccGraph(sccN);
    for (int i = 0; i < n; ++i) {
      int from = sccMap[i];
      for (int x : graph[i]) {
        int to = sccMap[x];
        if (from != to) {
          sccGraph[from].insert(to);
        }
      }
    }

    for (int i = 0; i < sccN; ++i) {
      for (int x : sccGraph[i]) {
        indegrees[x]++;
      }
    }

    int headNode = -1;
    for (int i = 0; i < sccN; ++i) {
      if (indegrees[i] == 0) {
        if (headNode < 0) {
          headNode = i;
        } else {
          headNode = -1;
          break;
        }
      }
    }

    if (headNode == -1) {
      return vector<int>();
    }
    vector<int>& result = sccNodes[headNode];
    sort(result.begin(), result.end());
    return result;
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> graph(n);
  vector<vector<int>> graphT(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    graph[b].push_back(a);
    graphT[a].push_back(b);
  }
  vector<int> result = Capcity().kosaraju(graph, graphT);
  cout << result.size() << endl;
  if (result.empty()) {
    return 0;
  }
  cout << (result[0] + 1);
  for (int i = 1; i < result.size(); ++i) {
    cout << " " << (result[i] + 1);
  }
  cout << endl;
  return 0;
}