[AGC064] B - Red and Blue Spanning Tree

[Q] https://atcoder.jp/contests/agc064/tasks/agc064_b

解法が見えなかったので、とりあえず確実にありうることをポンポン実装していく150分だった。結果75/77ACまでしたけどダメだった。

考察
1. 条件が2つ。色条件を満たしていることと、連結であること。
色条件がかなり厳しそう。
連結かどうかは、UnionFindで適当にuniteしていけばいいから後回し。

2. N頂点に対してN-1辺しかない。
1辺で1頂点の色を満たすように張るのでは、N-1頂点の色しか満たせない。1つ足りない。効率よく色を網羅したい。
1辺で2頂点の色を網羅するような辺を、少なくとも1つ設置する必要がある。
S[a] == c && S[b] == cとなる辺a-bを、まず張る。
これは1辺だけでなく、存在する限りいくらでも設置していい。

3.  どうやら、2.の頂点をスタート地点にして、枝を伸ばすように森を構築していく必要があるようだ。
伸ばす先の頂点は色条件を満たすように張る必要がある。
aをスタート地点として、S[b] == cとなるような辺a-bだけを伸ばす。
森がたくさんできるはず。

4. 最後に木にする。M辺全てについて、辺を張ったら連結成分が増えるかどうか確認。増えるなら設置すればいい。
見つけた順に適当でいい。

Q. 枝を伸ばす感じではなく、とにかく色を満たす辺をぽつぽつ設置するのは？
A. ダメ。cycleという名前の2ケースに永遠に落ち続ける。なんかダメなんだろう。

実装

int main() {
  cincout();
  ll N, M;
  cin >> N >> M;
  // G[i][0] = Rの次の辺 G[i][1] = Bの次の辺
  vector<vector<vector<ll>>> G(N, vector<vector<ll>>(2));
  map<tll, ll> memo;
  rep(i, M) {
    ll a, b;
    char c;
    cin >> a >> b >> c;
    --a, --b;
    G[a][c == 'B'].emplace_back(b);
    G[b][c == 'B'].emplace_back(a);
    memo[{a, b, c == 'B'}] = i;
    memo[{b, a, c == 'B'}] = i;
  }
  string S;
  cin >> S;
  vector<ll> SS(N);
  rep(i, N) SS[i] = S[i] == 'B';
 
  UnionFind tree(N);
  queue<ll> Q;
  vector<ll> ans;
  bool ok[N]{};

  // 1辺で2頂点塗れるいいところを探す
  for(auto [t, v]: memo){
    auto [a, b, c] = t;
    // この辺を採用すると、2頂点の色条件をクリアできる。
    if (ok[a] || ok[b]) continue;
    if (SS[a] == c && SS[b] == c){
      tree.unite(a, b);
      ok[a] = true;
      ok[b] = true;
      Q.push(a); // 枝を伸ばすスタート地点を押さえておく。
      Q.push(b);
      ans.emplace_back(v);
    }
  }

  // 森を構築
  while(!Q.empty()){
    ll v = Q.front(); Q.pop();
    rep(j, 2){
      for(auto u: G[v][j]){
        if (ok[u]) continue;
        // 伸ばした先の色条件をクリアしているかどうか。
        if (SS[u] != j) continue;
        ok[u] = true;
        tree.unite(v, u);
        ans.emplace_back(memo[{v, u, j}]);
        Q.push(u);
      }
    }
  }

  // 適当に連結にする
  for(auto [t, v]: memo){
    auto [a, b, c] = t;
    if (tree.issame(a, b)) continue;
    tree.unite(a, b);
    ans.emplace_back(v);
  }
  if (tree.getSize(0) != N){
    cout << "No" << endl;
    return 0;
  }
  rep(i, N){
    if (!ok[i]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  sort(all(ans));
  rep(i, N - 1) cout << (ans[i] + 1) << " \n"[i == N - 2];
}

https://atcoder.jp/contests/agc064/submissions/44571572

適当に構築してよいものと、いけないものとの判別ができなかった。