#[derive(Default)]
struct Graph {
n: usize,
m: usize,
head: Vec<usize>,
next: Vec<usize>,
src: Vec<usize>,
dst: Vec<usize>,
weight: Vec<isize>,
}
impl Graph {
fn new(n: usize) -> Graph {
Graph { n: n, m: 0, head: vec![!0; n], .. Default::default() }
}
fn add_edge(&mut self, u: usize, v: usize, w: isize) -> usize {
self.next.push(self.head[u]);
self.src.push(u);
self.dst.push(v);
self.weight.push(w);
self.head[u] = self.m;
self.m += 1;
self.m
}
}
struct UnionFind {
parent: Vec<usize>,
size: Vec<usize>,
}
impl UnionFind {
fn new(n: usize) -> UnionFind {
UnionFind { parent: vec![!0;n], size: vec![1;n] }
}
fn root(&mut self, u: usize) -> usize {
if self.parent[u] == !0 {
u
} else {
let p = self.parent[u];
self.parent[u] = self.root(p);
self.parent[u]
}
}
fn unite(&mut self, u: usize, v: usize) -> bool {
let mut u = self.root(u);
let mut v = self.root(v);
if u == v {
return false;
}
if self.size[u] > self.size[v] {
std::mem::swap(&mut u, &mut v);
}
self.parent[v] = u;
self.size[u] += self.size[v];
true
}
}
fn kruskal(g: Graph) -> Graph {
let mut es: Vec<usize> = (0..g.m).collect();
es.sort_by_key(|&i| g.weight[i]);
let mut mst = Graph::new(g.n);
let mut uf = UnionFind::new(g.n);
// for e in es { // <- es を消費してしまうので NG (thx: @qnighty)
for &e in &es {
if uf.unite(g.src[e], g.dst[e]) {
mst.add_edge(g.src[e], g.dst[e], g.weight[e]);
}
}
return mst;
}
fn main() {
let mut g = Graph::new(5);
g.add_edge(0,1,3);
g.add_edge(1,2,1);
g.add_edge(2,3,4);
g.add_edge(3,4,1);
g.add_edge(4,0,5);
let mst = kruskal(g);
for e in 0 .. mst.m {
println!("({},{},{})", mst.src[e], mst.dst[e], mst.weight[e])
}
}
I1tkZXJpdmUoRGVmYXVsdCldCgpzdHJ1Y3QgR3JhcGggewogIG46IHVzaXplLAogIG06IHVzaXplLAogIGhlYWQ6IFZlYzx1c2l6ZT4sCiAgbmV4dDogVmVjPHVzaXplPiwKICBzcmM6IFZlYzx1c2l6ZT4sCiAgZHN0OiBWZWM8dXNpemU+LAogIHdlaWdodDogVmVjPGlzaXplPiwKfQoKaW1wbCBHcmFwaCB7CiAgZm4gbmV3KG46IHVzaXplKSAtPiBHcmFwaCB7CiAgICBHcmFwaCB7IG46IG4sIG06IDAsIGhlYWQ6IHZlYyFbITA7IG5dLCAuLiBEZWZhdWx0OjpkZWZhdWx0KCkgfQogIH0KICBmbiBhZGRfZWRnZSgmbXV0IHNlbGYsIHU6IHVzaXplLCB2OiB1c2l6ZSwgdzogaXNpemUpIC0+IHVzaXplIHsKICAgIHNlbGYubmV4dC5wdXNoKHNlbGYuaGVhZFt1XSk7CiAgICBzZWxmLnNyYy5wdXNoKHUpOwogICAgc2VsZi5kc3QucHVzaCh2KTsKICAgIHNlbGYud2VpZ2h0LnB1c2godyk7CiAgICBzZWxmLmhlYWRbdV0gPSBzZWxmLm07CiAgICBzZWxmLm0gKz0gMTsKICAgIHNlbGYubQogIH0KfQoKc3RydWN0IFVuaW9uRmluZCB7CiAgcGFyZW50OiBWZWM8dXNpemU+LAogIHNpemU6IFZlYzx1c2l6ZT4sCn0KaW1wbCBVbmlvbkZpbmQgewogIGZuIG5ldyhuOiB1c2l6ZSkgLT4gVW5pb25GaW5kIHsKICAgIFVuaW9uRmluZCB7IHBhcmVudDogdmVjIVshMDtuXSwgc2l6ZTogdmVjIVsxO25dIH0KICB9CiAgZm4gcm9vdCgmbXV0IHNlbGYsIHU6IHVzaXplKSAtPiB1c2l6ZSB7CiAgICBpZiBzZWxmLnBhcmVudFt1XSA9PSAhMCB7CiAgICAgIHUKICAgIH0gZWxzZSB7CiAgICAgIGxldCBwID0gc2VsZi5wYXJlbnRbdV07CiAgICAgIHNlbGYucGFyZW50W3VdID0gc2VsZi5yb290KHApOwogICAgICBzZWxmLnBhcmVudFt1XQogICAgfQogIH0KICBmbiB1bml0ZSgmbXV0IHNlbGYsIHU6IHVzaXplLCB2OiB1c2l6ZSkgLT4gYm9vbCB7CiAgICBsZXQgbXV0IHUgPSBzZWxmLnJvb3QodSk7CiAgICBsZXQgbXV0IHYgPSBzZWxmLnJvb3Qodik7CiAgICBpZiB1ID09IHYgeyAKICAgICAgcmV0dXJuIGZhbHNlOwogICAgfQogICAgaWYgc2VsZi5zaXplW3VdID4gc2VsZi5zaXplW3ZdIHsKICAgICAgc3RkOjptZW06OnN3YXAoJm11dCB1LCAmbXV0IHYpOwogICAgfQogICAgc2VsZi5wYXJlbnRbdl0gPSB1OwogICAgc2VsZi5zaXplW3VdICs9IHNlbGYuc2l6ZVt2XTsKICAgIHRydWUKICB9Cn0KCmZuIGtydXNrYWwoZzogR3JhcGgpIC0+IEdyYXBoIHsKICBsZXQgbXV0IGVzOiBWZWM8dXNpemU+ID0gKDAuLmcubSkuY29sbGVjdCgpOwogIGVzLnNvcnRfYnlfa2V5KHwmaXwgZy53ZWlnaHRbaV0pOwoKICBsZXQgbXV0IG1zdCA9IEdyYXBoOjpuZXcoZy5uKTsKICBsZXQgbXV0IHVmID0gVW5pb25GaW5kOjpuZXcoZy5uKTsKICAvLyBmb3IgZSBpbiBlcyB7IC8vIDwtIGVzIOOCkua2iOiyu+OBl+OBpuOBl+OBvuOBhuOBruOBpyBORyAodGh4OiBAcW5pZ2h0eSkKICBmb3IgJmUgaW4gJmVzIHsKICAgIGlmIHVmLnVuaXRlKGcuc3JjW2VdLCBnLmRzdFtlXSkgewogICAgICBtc3QuYWRkX2VkZ2UoZy5zcmNbZV0sIGcuZHN0W2VdLCBnLndlaWdodFtlXSk7CiAgICB9CiAgfQogIHJldHVybiBtc3Q7Cn0KCmZuIG1haW4oKSB7CiAgbGV0IG11dCBnID0gR3JhcGg6Om5ldyg1KTsKICBnLmFkZF9lZGdlKDAsMSwzKTsKICBnLmFkZF9lZGdlKDEsMiwxKTsKICBnLmFkZF9lZGdlKDIsMyw0KTsKICBnLmFkZF9lZGdlKDMsNCwxKTsKICBnLmFkZF9lZGdlKDQsMCw1KTsKICBsZXQgbXN0ID0ga3J1c2thbChnKTsKICBmb3IgZSBpbiAwIC4uIG1zdC5tIHsKICAgIHByaW50bG4hKCIoe30se30se30pIiwgbXN0LnNyY1tlXSwgbXN0LmRzdFtlXSwgbXN0LndlaWdodFtlXSkKICB9Cn0K