読者です 読者をやめる 読者になる 読者になる

SRM608 Div2Hard BigOEasy

問題概要
ある有向グラフが与えられる。このグラフをたどるとき、そのパスの数が多項式の距離で表されるかどうか判定せよ。一度通ったノードでもパスがあれば何度でも通ることが出来る。

解法
i から到達できる j を全て探す。中継点kを決めるN^3の方式で、判定を重ねると到達できるノードが順に増えていく。
すると i -> 中継点 k(≠i) -> i と進む経路があるかどうかがわかる。つまり閉路を全て数え上げることが出来る。
よって閉路の数が1より大きくなれば "Unbounded" であり、そうでなければ "Bounded" となる

蛇足だがC++11では bool に対する operator |= が定義されていない。"または"ではなく論理和なので、確かに定義されてないほうが正しいと思った。

class BigOEasy {
public:
  string isBounded(vector <string> graph) {
    int const N = graph.size();
    vector<vector<bool>> mat(N, vector<bool>(N, false));
    
    for(int i=0; i<N; i++)
      for(int j=0; j<N; j++)
        mat[i][j] = graph[i][j] == 'Y';
    
    for(int k=0; k<N; k++)
      for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
          mat[i][j] = mat[i][j] || (mat[i][k]&&mat[k][j]);

    for(int i=0; i<N; i++) {
      int cnt = 0;
      for(int k=0; k<N; k++) {
        if(i == k) continue;
        cnt += (graph[i][k]=='Y') && mat[k][i];
      }
      if(cnt > 1) return "Unbounded";
    }
    
    return "Bounded";
  }
};