D - Unicyclic Components Editorial by ngtkana


答えは、\(N = M\) かつすべての連結成分がサイクルを持つことです。

超頂点 \(\star\) を一つ追加して union-find をし、普通に辺を追加した後で、それで(超頂点なしのほうのグラフで)サイクルができた場合には \(\star\) ともつなぐことにして、最後に全体が連結になっているかどうかを見ればよいです。

超頂点なしのほうのグラフでサイクルができたかどうかの判定は、実は超頂点ありの方で判定した結果と同じになりますから、簡単に判定ができます。(証明は難しくありませんが、自明ではありません。)

Rust 32 ms

use petgraph::unionfind::UnionFind;
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        m: usize,
        edges: [(Usize1, Usize1); m],
    }
    let mut uf = UnionFind::new(n + 1);
    for &(i, j) in &edges {
        if !uf.union(i, j) {
            uf.union(i, n);
        }
    }
    let ans = n == m && (0..n).all(|i| uf.equiv(i, n));
    println!("{}", ["No", "Yes"][ans as usize]);
}

posted:
last update: