PAST #12 K

PAST #12 第12回 アルゴリズム実技検定 過去問

• K - 連結チェック https://atcoder.jp/contests/past202209-open/tasks/past202209_k
  • 提出: https://atcoder.jp/contests/past202209-open/submissions/48060633
  • 同一連結成分かを高速に判定するなら Dsu (Union-Find)
  • ただし Dsu は連結はできてもその逆はできない
  • そこで逆向きに走査する (最終状態からはじめて削除のかわりに追加していく)
  • t_i = 1 のケースは 10 個以下なので再度 Dsu を作り直しても間に合う

use std::collections::HashSet;

use ac_library::Dsu;
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        m: usize,
        ab: [(Usize1, Usize1); m],
        q: usize,
        txy: [(usize, Usize1, Usize1); q],
    };
    let mut edges = HashSet::new();
    for (a, b) in ab.iter().copied() {
        edges.insert((a.min(b), a.max(b)));
    }
    for (t, x, y) in txy.iter().copied() {
        match t {
            1 => {
                edges.insert((x.min(y), x.max(y)));
            }
            2 => {
                edges.remove(&(x.min(y), x.max(y)));
            }
            3 => {
                // do nothing
            }
            _ => unreachable!(),
        }
    }

    let mut dsu = Dsu::new(n);
    for (a, b) in edges.iter().copied() {
        dsu.merge(a, b);
    }

    let mut ans = vec![];
    for (t, x, y) in txy.iter().copied().rev() {
        match t {
            1 => {
                edges.remove(&(x.min(y), x.max(y)));
                // rebuild dsu
                dsu = Dsu::new(n);
                for (a, b) in edges.iter().copied() {
                    dsu.merge(a, b);
                }
            }
            2 => {
                edges.insert((x.min(y), x.max(y)));
                dsu.merge(x, y);
            }
            3 => {
                ans.push(dsu.same(x, y));
            }
            _ => unreachable!(),
        }
    }
    for a in ans.into_iter().rev() {
        println!("{}", if a { "Yes" } else { "No" });
    }
}

---

今日のコミット。

• kireta 1 commit
  • Add FirestoreStore::find_all_items test
• rust-atcoder 1 commit
  • past202209-open k