教学网站的设计,网站安全证书过期怎么办,如何查询企业邮箱,有哪些做实验的参考网站并查集题目 聚合一块#xff08;蓝桥#xff09;合根植物#xff08;蓝桥#xff09;等式方程的可满足性省份数量 并查集#xff08;Union-Find#xff09;算法是一个专门针对「动态连通性」的算法。双方向的连通。 模板#xff1a;
class UF {// 连通分量个数private … 并查集题目 聚合一块蓝桥合根植物蓝桥等式方程的可满足性省份数量 并查集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 nscan.nextInt();int mscan.nextInt();UF ufnew UF(n1);for(int i0;im;i){int qscan.nextInt();int pscan.nextInt();uf.union(q,p);}System.out.println(uf.count-2);scan.close();}
}
class UF{//连通分量个数int count;//存储每个节点的父节点int[]parent;//创建n个节点的连通图UF(int n){this.countn;parentnew int[n];for(int i1;in;i){parent[i]i;}}//将p和q联通void union(int p,int q){int rootPfind(p);int rootQfind(q);if(rootProotQ){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 mscan.nextInt();int nscan.nextInt();UF ufnew UF(m*n1);int kscan.nextInt();for(int i0;ik;i){int ascan.nextInt();int bscan.nextInt();uf.union(a,b);}System.out.println(uf.count-1);scan.close();}
}
class UF{int count;int[] parent;UF(int n){this.countn;parentnew int[n];for(int i1;in;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 rootQfind(q);int rootPfind(p);if(rootProotQ){return;}parent[rootP]rootQ;count--;}
}等式方程的可满足性
题目 思路先执行“ ”的式子 连通“”两边的字母。后来执行“! ”的式子判断“! ”两边的字母是否连通如果连通就返回false。 class Solution {public boolean equationsPossible(String[] equations) {UF ufnew UF(26);//先排一下序使先执行“”!的ASCLL较小输出从大到小后-前Arrays.sort(equations, new ComparatorString() {Overridepublic int compare(String o1, String o2) {return o2.charAt(1)-o1.charAt(1);}});for(String ele:equations){int qele.charAt(0)-a;int pele.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.countn;parentnew int[n];for(int i0;in;i){parent[i]i;}}void union(int q,int p){int rootQfind(q);int rootPfind(p);if(rootProotQ){return;}parent[rootP]rootQ;count--;}boolean isConnected(int q,int p){int rootQfind(q);int rootPfind(p);return rootProotQ;}int find(int x){if(x!parent[x]){parent[x]find(parent[x]);}return parent[x];}
}省份数量
题目
class Solution {public int findCircleNum(int[][] isConnected) {int sizeisConnected.length;UF ufnew UF(size);for(int i0;isize;i){for(int ji1;jsize;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;}
}
