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"; } };