Checking Consistency of CS Curriculum

题目链接：pdf

题目给一个有向图，判断是不是有环。我的方法是DFS，对于一个点，访问的过程中存在这三种情况：

1. 访问v的过程中，再次访问到了v这个点，说明存在环。
2. 完成访问v后（DFS已经回退到v之后），以后再次访问到了v，这是没有问题 的，这种情况不能说明存在环。
3. v还没有访问过。

因此用三个不同的值来标记这三种情况就可以了。

// Fri May 12 22:50:22 CST 2017
// Fri May 12 23:50:02 CST 2017


// 判断一个有向图是不是有环。。。

#include <iostream>
#include <vector>

using namespace std;

/*
visit[i]的值有三种情况：
0:这个点没有访问过
1:这个点正在访问
2:这个点以及和它相连的点都已经访问过了

所以DFS的过程中，下一个点遇到了visit[e] == 1说明有环。
 */

void
dfs(vector<vector<int> > &adj, vector<int> &visit,
    int x, bool &mark)
{
  // cout << "(" << x + 1 << ", " << num << ")" << "\n";
  visit[x] = 1;
  if (mark) return;

  for (auto e : adj[x]) {
    if (mark) return;
    else if (visit[e] == 1) {
      mark = true;
      return;
    }
    else if (!visit[e]) {
      dfs(adj, visit, e, mark);
    }
  }

  visit[x] = 2;
}

int
acyclic(vector<vector<int> > &adj, int n) {
  vector<int> visit(n, 0);
  bool mark = false;

  for (size_t i = 0; i < adj.size(); ++i) {
    if (!visit[i]) {
      dfs(adj, visit, i, mark);
    }
    if (mark) break;
  }
  
  return (mark ? 1 : 0);
}

int main() {
  size_t n, m;
  // cin >> n >> m;
  while(std::cin >> n >> m) {
  vector<vector<int> > adj(n, vector<int>());
  
  for (size_t i = 0; i < m; i++) {
    int x, y;
    std::cin >> x >> y;
    adj[x - 1].push_back(y - 1);
  }
  std::cout << acyclic(adj, n) << endl;
  }

  return 0;
}