spoj_capacity_tarjan.cpp

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

using namespace std;

class Capcity {
private:
  void dfs(
    vector<vector<int>>& graph,
    int root,
    vector<int>& indices,
    vector<int>& lowIndices,
    vector<vector<int>>& sccNodes,
    stack<int>& st,
    vector<bool>& onStack,
    int& index
  ) {
    // visited
    if (indices[root] >= 0) {
      return;
    }
    indices[root] = index;
    lowIndices[root] = index;
    st.push(root);
    onStack[root] = true;
    ++index;
    for (int next : graph[root]) {
      if (indices[next] < 0) {
        dfs(graph, next, indices, lowIndices, sccNodes, st, onStack, index);
        lowIndices[root] = min(lowIndices[next], lowIndices[root]);
      } else if (onStack[next]) {
        lowIndices[root] = min(lowIndices[root], indices[next]);
      }
    }
    if (lowIndices[root] == indices[root]) {
      vector<int> component;
      int top = -1;
      do {
        top = st.top();
        st.pop();
        component.push_back(top);
        onStack[top] = false;
      } while (top != root);
      sccNodes.push_back(component);
    }
  }
public:
  vector<int> tarjan(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> indices(n, -1);
    vector<int> lowIndices(n, -1);
    stack<int> st;
    vector<vector<int>> sccNodes;
    vector<bool> onStack(n, false);
    int index = 0;
    for (int i = 0; i < n; ++i) {
      dfs(graph, i, indices, lowIndices, sccNodes, st, onStack, index);
    }
    int sccN = sccNodes.size();
    vector<int> sccMap(n);
    vector<int> indegrees(n, 0);
    for (int i = 0; i < sccNodes.size(); ++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);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    graph[b].push_back(a);
  }
  vector<int> result = Capcity().tarjan(graph);
  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;
}