首页 > 代码库 > 【Union Find】JAVA implementation
【Union Find】JAVA implementation
import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.Scanner; class UF { private int[] id; private int count; public UF(int N) { count = N; id = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; } } public int count(){ return count; } public int find(int p){ while (p != id[p]) { p = id[p]; } return p; } public boolean connected(int p, int q){ return find(p) == find(q); } public void union(int p, int q){ int proot = find(p); int qroot = find(q); if (proot == qroot) { return; } id[proot] = qroot; count--; } public String toString() { return Arrays.toString(id); } } public class Main { public static void main(String[] args) { Scanner jin = new Scanner(System.in); int N = jin.nextInt(); UF uf = new UF(N); while (jin.hasNext()) { int p = jin.nextInt(); int q = jin.nextInt(); if (uf.connected(p, q)) { continue; } uf.union(p, q); } System.out.println(uf.count()); System.out.println(uf); } }
对两棵树的合并操作做优化,引入变量size表示这棵树的结点个数,合并时,总是使size小的链接到size大的树。这样合并得到的森林,如果有N个结点,那么树的深度
不会超过lgN。
import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.Scanner; class UF { private int[] id; private int[] size; private int count; public UF(int N) { count = N; id = new int[N]; size = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; size[i] = 1; } } public int count(){ return count; } public int find(int p){ while (p != id[p]) { p = id[p]; } return p; } public boolean connected(int p, int q){ return find(p) == find(q); } public void union(int p, int q){ int proot = find(p); int qroot = find(q); if (proot == qroot) { return; } if (size[proot] < size[qroot]) { id[proot] = qroot; size[qroot] += size[proot];} else {id[qroot] = proot; size[proot] += size[qroot];} count--; } public String toString() { return Arrays.toString(id); } } public class Main { public static void main(String[] args) { Long n; //System.out.println(Long.MAX_VALUE); Scanner jin = new Scanner(System.in); int N = jin.nextInt(); UF uf = new UF(N); while (jin.hasNext()) { int p = jin.nextInt(); int q = jin.nextInt(); if (uf.connected(p, q)) { continue; } uf.union(p, q); } System.out.println(uf.count()); System.out.println(uf); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。