AOJ2555 Everlasting Zero

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2555

N個のスキルがあり、それぞれについて初めの経験値は0である。
あるコマンドを覚えるためには、指定された複数のスキルの経験値が条件を満たす必要がある。
条件は、スキルi >= 3, スキルj <= 7 といったように与えられる。
スキルi <=5 かつ スキルi >= 7 のように、条件に矛盾も存在する。
すべてのコマンドを覚えることが可能か判定せよ。

解説
まず、各コマンドについて条件の矛盾が有れば、その時点で不可能となる。
次に、全てのコマンドを覚えることのできる順序があるかどうか判定する。
例えば、コマンドxではスキルi <= 3の条件があり、コマンドyではスキルi >=7の条件があるとすると、コマンドyはコマンドxを覚えた後に覚える必要がある。
また、例えばコマンドxではスキルi >= 3、コマンドyではスキルi >= 4 かつスキルi <= 5 であるとすると、コマンドxとyのどちらを先に覚えるべきかは、この条件からは決まらない。

言い換えると、コマンドx, yについて、スキルiの満たすべき経験値の区間が重ならなければ、コマンドx, yの間に順序関係を定義できる。

その順序関係に矛盾が生じるというのは、順序関係を有向グラフにしたときに閉路が出来ることと同義である。

よって、順序関係をグラフにした後、各連結成分がDAGとなっているかどうか判定すれば良い。
DAGの判定はDFSでもよいし、辺のコストを負にしておいてベルマンフォードで負のループを見つけても良い。

bool isDAG(vector<vector<int>>& G) {
  int N = G.size();
  vector<bool> vis(N);
 
  std::function<bool(int, unordered_set<int>&)> dfs = [&](int curr, unordered_set<int>& st) {
    for(auto&& e: G[curr]) {
      if(st.count(e)) return false;
      if(vis[e]) continue;
      st.insert(e);
      vis[e] = 1;
      if(!dfs(e, st)) return false;
      st.erase(e);
    }
    return true;
  };
 
  rep(e, N) {
    vis[e] = 1;
    unordered_set<int> st = {e};
    if(!dfs(e, st)) return false;
  }
  return true;
}
 
int main() {
 
  int M, N; cin >> M >> N;
  vector<vector<pair<int, int>>> cmd_sect(N, vector<pair<int, int>>(M, {0, inf}));
 
  rep(cmd_idx, M) {
    int K; cin >> K;
    rep(_, K) {
      int skill; cin >> skill; skill--;
      string op; cin >> op;
      int threshold; cin >> threshold;
      if(op == ">=") {
        cmd_sect[skill][cmd_idx].first = max(cmd_sect[skill][cmd_idx].first, threshold);
      } else {
        cmd_sect[skill][cmd_idx].second = min(cmd_sect[skill][cmd_idx].second, threshold);
      }
      if(cmd_sect[skill][cmd_idx].first > cmd_sect[skill][cmd_idx].second) {
        cout << "No" << endl;
        return 0;
      }
    }
  }
 
  vector<vector<int>> G(M);
   
  rep(i, N) {
    rep(a, M) rep(b, M) {
      if(a == b) continue;
      if(cmd_sect[i][a].second < cmd_sect[i][b].first)
        G[a].push_back(b);
    }
  }
 
  rep(i, M) {
    sort(all(G[i]));
    G[i].erase(unique(all(G[i])), G[i].end());
  }
 
  cout << (isDAG(G) ? "Yes" : "No") << endl;
 
  return 0;
}