并查集 UnionFind Test01
1. 是什么？
一种很不一样的树形结构
- 一般的结构是父亲指向孩子（比如说二叉树）;
- 而并查集是孩子指向父亲
2. 解决什么问题？ 主要来解决连接问题
*接口定义*
public interface UF {int getSize();boolean isConnected(int p, int q);void unionElements(int p, int q);}6个版本实现并查集
public class UnionFind1 implements UF {private int[] id;public UnionFind1(int size) {id = new int[size];for (int i = 0; i < size; i++) {id[i] = i;}}@Overridepublic int getSize() {return id.length;}private int find(int p) {return id[p];}public boolean isConnected(int p, int q) {return find(p) == find(q);}@Overridepublic void unionElements(int p, int q) {int pId = find(p);int qId = find(q);if (pId == qId) {return;}for (int i = 0; i < id.length; i++) {if (id[i] == pId) {id[i] = qId;}}}}
*quick union *`` public class UnionFind2 implements UF {
``
`` private int[] parent;
``
`` public UnionFind2(int size) {
`` parent = new int[size];
`` for (int i = 0; i < size; i++) {
`` parent[i] = i;
`` }
`` }
``
`` @Override
`` public int getSize() {
`` return parent.length;
`` }
``
`` private int find(int p) {
``
`` while (p != parent[p]) {
`` p = parent[p];
`` }
`` return p;
`` }
``
`` @Override
`` public boolean isConnected(int p, int q) {
`` return find(p) == find(q);
`` }
``
`` @Override
`` public void unionElements(int p, int q) {
``
`` int pRoot = find(p);
`` int qRoot = find(q);
`` if (qRoot == pRoot) {
`` return;
`` }
`` parent[pRoot] = qRoot;
`` }
`` }*quick union 基于size的优化*`` public class UnionFind3 implements UF {
``
`` //基于size的优化
`` private int[] parent;
``
`` private int[] sz;
``
`` public UnionFind3(int size) {
`` parent = new int[size];
`` sz = new int[size];
`` for (int i = 0; i < size; i++) {
`` parent[i] = i;
`` sz[i] = 1;
`` }
`` }
``
`` @Override
`` public int getSize() {
`` return parent.length;
`` }
``
`` private int find(int p) {
``
`` while (p != parent[p]) {
`` p = parent[p];
`` }
`` return p;
`` }
``
`` @Override
`` public boolean isConnected(int p, int q) {
`` return find(p) == find(q);
`` }
``
`` @Override
`` public void unionElements(int p, int q) {
``
`` int pRoot = find(p);
`` int qRoot = find(q);
`` if (qRoot == pRoot) {
`` return;
`` }
`` if (sz[qRoot] > sz[pRoot]) {
`` parent[pRoot] = qRoot;
`` sz[qRoot] += sz[pRoot];
`` }else {
`` parent[qRoot] = pRoot;
`` sz[pRoot] += sz[qRoot];
`` }
``
`` }
`` }*quick union 基于rank 的优化*`` public class UnionFind4 implements UF {
``
`` //基于rank的优化
`` private int[] parent;
``
`` private int[] rank;
``
`` public UnionFind4(int size) {
`` parent = new int[size];
`` rank = new int[size];
`` for (int i = 0; i < size; i++) {
`` parent[i] = i;
`` rank[i] = 1;
`` }
`` }
``
`` @Override
`` public int getSize() {
`` return parent.length;
`` }
``
`` private int find(int p) {
``
`` while (p != parent[p]) {
`` p = parent[p];
`` }
`` return p;
`` }
``
`` @Override
`` public boolean isConnected(int p, int q) {
`` return find(p) == find(q);
`` }
``
`` @Override
`` public void unionElements(int p, int q) {
``
`` int pRoot = find(p);
`` int qRoot = find(q);
`` if (qRoot == pRoot) {
`` return;
`` }
`` if (rank[qRoot] > rank[pRoot]) {
`` parent[pRoot] = qRoot;
`` } else if (rank[qRoot] < rank[pRoot]) {
`` parent[qRoot] = pRoot;
`` }else {
`` parent[pRoot] = qRoot;
`` rank[qRoot]++;
`` }
``
`` }
`` }*quick union 路径压缩版本1*`` public class UnionFind5 implements UF {
``
`` //基于路径压缩的优化 ->我们希望树的结构越简单越好，越扁平越好
`` //在find的时候进行压缩操作
`` private int[] parent;
``
`` private int[] rank;
``
`` public UnionFind5(int size) {
`` parent = new int[size];
`` rank = new int[size];
`` for (int i = 0; i < size; i++) {
`` parent[i] = i;
`` rank[i] = 1;
`` }
`` }
``
`` @Override
`` public int getSize() {
`` return parent.length;
`` }
``
`` private int find(int p) {
``
`` while (p != parent[p]) {
`` parent[p] = parent[parent[p]];
`` p = parent[p];
`` }
`` return p;
`` }
``
`` @Override
`` public boolean isConnected(int p, int q) {
`` return find(p) == find(q);
`` }
``
`` @Override
`` public void unionElements(int p, int q) {
``
`` int pRoot = find(p);
`` int qRoot = find(q);
`` if (qRoot == pRoot) {
`` return;
`` }
`` if (rank[qRoot] > rank[pRoot]) {
`` parent[pRoot] = qRoot;
`` } else if (rank[qRoot] < rank[pRoot]) {
`` parent[qRoot] = pRoot;
`` }else {
`` parent[pRoot] = qRoot;
`` rank[qRoot]++;
`` }
``
`` }
`` }*quick union 路径压缩版本2*`` public class UnionFind6 implements UF {
``
`` //基于路径压缩的优化 ->我们希望树的结构越简单越好，越扁平越好
`` //在find的时候进行压缩操作
`` private int[] parent;
``
`` private int[] rank;
``
`` public UnionFind6(int size) {
`` parent = new int[size];
`` rank = new int[size];
`` for (int i = 0; i < size; i++) {
`` parent[i] = i;
`` rank[i] = 1;
`` }
`` }
``
`` @Override
`` public int getSize() {
`` return parent.length;
`` }
``
`` private int find(int p) {
``
`` if (p != parent[p]) {
`` parent[p] = find(parent[p]);
`` }
`` return parent[p];
`` }
``
`` @Override
`` public boolean isConnected(int p, int q) {
`` return find(p) == find(q);
`` }
``
`` @Override
`` public void unionElements(int p, int q) {
``
`` int pRoot = find(p);
`` int qRoot = find(q);
`` if (qRoot == pRoot) {
`` return;
`` }
`` if (rank[qRoot] > rank[pRoot]) {
`` parent[pRoot] = qRoot;
`` } else if (rank[qRoot] < rank[pRoot]) {
`` parent[qRoot] = pRoot;
`` }else {
`` parent[pRoot] = qRoot;
`` rank[qRoot]++;
`` }
``
`` }
`` }