[ARC164] B - Switching Travel

[Q] https://atcoder.jp/contests/arc164/tasks/arc164_b

7回間違えちゃった、グロすぎる。。
Cのほうが素直な問題でした。先に解いてから戻ってきました。

考察

Yesパターン

・出発点は、rootではなくて任意の頂点です。問題をよく読みましょう…。
・出発点の候補は、隣同士が同じ色の頂点。
・候補の頂点から、素直にdfsで白->黒->…と移動したときに、戻ってこれるかどうか確かめればよい。

実装

int main() {
  cincout();

  ll N, M;
  cin >> N >> M;
  vector<ll> G[N];
  vector<pll> edge(M);  // 辺をキープ。出発候補の頂点を調べる
  rep(i, M) {
    ll a, b;
    cin >> a >> b;
    --a, --b;
    G[a].push_back(b);
    G[b].push_back(a);
    edge[i] = {a, b};
  }
  vector<ll> color(N, 0);
  rep(i, N) cin >> color[i];
  vector<bool> cand(N, false);  // 出発候補点
  rep(i, M) {
    auto [a, b] = edge[i];
    if (color[a] == color[b]) {
      cand[a] = true;
      cand[b] = true;
    }
  }
  function<bool(ll, ll)> dfs = [&](ll v, ll start) {
    for (auto nv : G[v]) {
      if (color[nv] == color[v]) continue;
      if (nv == start) return true;
      color[v] ^= 1;
      if (dfs(nv, start)) return true;
      // バックトラック
      color[v] ^= 1;
    }
    return false;
  };

  rep(i, N) {
    if (cand[i]) {
      if (dfs(i, i)) { // {current, start}
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
}

https://atcoder.jp/contests/arc164/submissions/43431263