WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM618 Div1 Easy "Family"

問題

TopCoder Statistics - Problem Statement

下記のようなルールを満たす、有向な非循環のグラフはfamily graphであるとする。

  • グラフのノードには0からN-1の番号が付けられている。
  • それぞれのノードは男か女である。
  • それぞれのノードは、親がいないか、2人の親がを持つかのどちらかである。
(ノードxの親がノードyだとすると、yからxに向かってエッジが張られている)
  • ノードに親が存在する場合、親の番号は子の番号よりも小さい。
  • ノードに親が存在する場合、片方は男で、片方は女である。

あなたはともに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";
    }
};