并查集题目

并查集（Union-Find）算法是一个专门针对「动态连通性」的算法。双方向的连通。

模板：

class UF {// 连通分量个数private int count;// 存储每个节点的父节点private int[] parent;// n 为图中节点的个数public UF(int n) {this.count = n;parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}// 将节点 p 和节点 q 连通public void union(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP == rootQ)return;parent[rootQ] = rootP;// 两个连通分量合并成一个连通分量count--;}// 判断节点 p 和节点 q 是否连通public boolean connected(int p, int q) {int rootP = find(p);int rootQ = find(q);return rootP == rootQ;}public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}// 返回图中的连通分量个数public int count() {return count;}
}

聚合一块（蓝桥）

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main{public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int n=scan.nextInt();int m=scan.nextInt();UF uf=new UF(n+1);for(int i=0;i<m;i++){int q=scan.nextInt();int p=scan.nextInt();uf.union(q,p);}System.out.println(uf.count-2);scan.close();}
}
class UF{//连通分量个数int count;//存储每个节点的父节点int[]parent;//创建n个节点的连通图UF(int n){this.count=n;parent=new int[n];for(int i=1;i<n;i++){parent[i]=i;}}//将p和q联通void union(int p,int q){int rootP=find(p);int rootQ=find(q);if(rootP==rootQ){return;}parent[rootQ]=rootP;count--;}int find(int x){if(parent[x]!=x){parent[x]=find(parent[x]);}return parent[x];}int count(){return count;}
}

合根植物（蓝桥）

题目

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此输入您的代码...int m=scan.nextInt();int n=scan.nextInt();UF uf=new UF(m*n+1);int k=scan.nextInt();for(int i=0;i<k;i++){int a=scan.nextInt();int b=scan.nextInt();uf.union(a,b);}System.out.println(uf.count-1);scan.close();}
}
class UF{int count;int[] parent;UF(int n){this.count=n;parent=new int[n];for(int i=1;i<n;i++){parent[i]=i;}}int find(int x){if(parent[x]!=x){parent[x]=find(parent[x]);}return parent[x];}void union(int q,int p){int rootQ=find(q);int rootP=find(p);if(rootP==rootQ){return;}parent[rootP]=rootQ;count--;}
}

等式方程的可满足性

题目

思路：先执行“= =”的式子， 连通“==”两边的字母。后来执行“! =”的式子，判断“! =”两边的字母是否连通，如果连通就返回false。

class Solution {public boolean equationsPossible(String[] equations) {UF uf=new UF(26);//先排一下序，使先执行“==”，!的ASCLL较小，输出从大到小，后-前Arrays.sort(equations, new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {return  o2.charAt(1)-o1.charAt(1);}});for(String ele:equations){int q=ele.charAt(0)-'a';int p=ele.charAt(3)-'a';if(ele.charAt(1)=='='){//连通q puf.union(q,p);}else{if(uf.isConnected(q,p)){return false;}}}return true;}
}
class UF{int count;int[]parent;UF(int n){this.count=n;parent=new int[n];for(int i=0;i<n;i++){parent[i]=i;}}void union(int q,int p){int rootQ=find(q);int rootP=find(p);if(rootP==rootQ){return;}parent[rootP]=rootQ;count--;}boolean isConnected(int q,int p){int rootQ=find(q);int rootP=find(p);return rootP==rootQ;}int find(int x){if(x!=parent[x]){parent[x]=find(parent[x]);}return parent[x];}
}

省份数量

题目

class Solution {public int findCircleNum(int[][] isConnected) {int size=isConnected.length;UF uf=new UF(size);for(int i=0;i<size;i++){for(int j=i+1;j<size;j++){if(isConnected[i][j]==1){uf.union(i,j);}}}return uf.count;}
}class UF {// 连通分量个数int count;// 存储每个节点的父节点private int[] parent;// n 为图中节点的个数public UF(int n) {this.count = n;parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}// 将节点 p 和节点 q 连通public void union(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP == rootQ)return;parent[rootQ] = rootP;// 两个连通分量合并成一个连通分量count--;}// 判断节点 p 和节点 q 是否连通public boolean connected(int p, int q) {int rootP = find(p);int rootQ = find(q);return rootP == rootQ;}public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}// 返回图中的连通分量个数public int count() {return count;}
}