SRM618 Div1 Easy "Family"
問題
TopCoder Statistics - Problem Statement
訳
下記のようなルールを満たす、有向な非循環のグラフはfamily graphであるとする。
- グラフのノードには0からN-1の番号が付けられている。
- それぞれのノードは男か女である。
- それぞれのノードは、親がいないか、2人の親がを持つかのどちらかである。
- ノードに親が存在する場合、親の番号は子の番号よりも小さい。
- ノードに親が存在する場合、片方は男で、片方は女である。
あなたはともにN個の要素を持つ2つのint配列 parent1, parent2が与えられる。それらはfamily graphである可能性がある、1つのグラフの状態を表している。i番目のノードに両親が存在しない場合、parent1[i]とparent2[i]が両方とも-1となっている。i番目のノードに両親が存在する場合、parent1[i]とparent2[i]は両親の番号を表している。
与えられたグラフがfamily graphになり得るのであれば、"Possible"を、そうでなければ"Impossible"を返せ。
制約
1 <= N <= 100
考えたこと
問題文に親子でエッジが張られていると書かれているが、これは落とし穴・・・。family graphにおいて、関係性があるのは親子ではなく夫婦である。夫婦同士で辺を張ると単なるグラフの2色塗り分け問題となる。
いやらしい問題やで・・
ソースコード
int N; bool G[105][105]; int C[105]; class Family { public: bool dfs(int v, int c) { C[v] = c; for (int i = 0; i < N; i++) { if (!G[v][i]) continue; if (C[i] == 0) { if(!dfs(i, -c)) return false; } else if(C[i] == c) { return false; } } return true; } string isFamily(vector <int> parent1, vector <int> parent2) { N = parent1.size(); memset(G, false, sizeof(G)); for (int i = 0; i < N; i++) { if (parent1[i] == -1) continue; G[parent1[i]][parent2[i]] = G[parent2[i]][parent1[i]] = true; } memset(C, 0, sizeof(C)); for (int i = 0; i < N; i++) { if (C[i] == 0) { if (!dfs(i, 1)) return "Impossible"; } } return "Possible"; } };