SRM618 div1 easy Family

考えたこと

サンプルのグラフを書いてみると、parent1[i]とparent2[i]が2つの異なる値で分類できれば可能であると判定できそうなことに気づく。これはparent1[i]とparent2[i]をつないだグラフが2部グラフであるかどうか判定すればできる。提出したら通った。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

VI g[105];
int color[105];

bool dfs(int v, int c) {
  color[v] = c;
  for(int i: g[v]) {
    if(color[i] == c) return false;
    if(color[i] == 0 && !dfs(i, -c)) return false;
  }
  return true;
}

class Family {
   public:
   string isFamily(vector <int> p1, vector <int> p2)
  {
    int n = p1.size();
    REP(i, n) {
      if(p1[i] == -1) continue;
      g[p1[i]].PB(p2[i]);
      g[p2[i]].PB(p1[i]);
    }

    REP(i, n) {
      if(!color[i]) {
        if(!dfs(i, 1)) {
          return "Impossible";
        }
      }
    }
    return "Possible";
  }
};