spoj_capacity_path_based.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<vector<int>>& sccNodes,
    stack<int>& s,
    stack<int>& p,
    vector<int>& sccMap,
    int& index
  ) {
    // visited
    if (indices[root] >= 0) {
      return;
    }
    indices[root] = index;
    p.push(root);
    s.push(root);
    ++index;
    for (int next : graph[root]) {
      if (indices[next] < 0) {
        dfs(graph, next, indices, sccNodes, s, p, sccMap, index);
      } else if (sccMap[next] < 0) {
        while (indices[p.top()] > indices[next]) {
          p.pop();
        }
      }
    }
    if (root == p.top()) {
      vector<int> component;
      int size = sccNodes.size();
      int top = -1;
      do {
        top = s.top();
        s.pop();
        sccMap[top] = size;
        component.push_back(top);
      } while (top != root);
      p.pop();
      sccNodes.push_back(component);
    }
  }
public:
  vector<int> pathBased(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> indices(n, -1);
    stack<int> s;
    stack<int> p;
    vector<vector<int>> sccNodes;
    vector<int> sccMap(n, -1);

    int index = 0;
    for (int i = 0; i < n; ++i) {
      dfs(graph, i, indices, sccNodes, s, p, sccMap, index);
    }
    int sccN = sccNodes.size();

    vector<int> indegrees(n, 0);

    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().pathBased(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;
}