D - Unicyclic Components Editorial by ngtkana
答えは、\(N = M\) かつすべての連結成分がサイクルを持つことです。
超頂点 \(\star\) を一つ追加して union-find をし、普通に辺を追加した後で、それで(超頂点なしのほうのグラフで)サイクルができた場合には \(\star\) ともつなぐことにして、最後に全体が連結になっているかどうかを見ればよいです。
超頂点なしのほうのグラフでサイクルができたかどうかの判定は、実は超頂点ありの方で判定した結果と同じになりますから、簡単に判定ができます。(証明は難しくありませんが、自明ではありません。)
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: