主机屋网站,如何寻找seo网站建设客户,html商务网站模板,北京一环都是住什么人前言
###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程#xff08;例如想要掌握基础用法#xff0c;该刷哪些题#xff1f;#xff09;我的解析也不会做的非常详细#xff0c;只会提供思路和一些关键点#xff0c;力扣上的大佬们的题解质量是非…前言
###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程例如想要掌握基础用法该刷哪些题我的解析也不会做的非常详细只会提供思路和一些关键点力扣上的大佬们的题解质量是非常非常高滴 1.统计无向图中无法互相到达点对数
题目链接:2316. 统计无向图中无法互相到达点对数 - 力扣LeetCode
题面:
代码:
class Solution {public long countPairs(int n, int[][] edges) {UF uf new UF(n);for (int[] edge : edges) {uf.union(edge[0], edge[1]);}int[] size uf.size();// 记录所有分支的大小ListInteger list new ArrayList();SetInteger set new HashSet();for (int i 0; i n; i) {// 找到节点 i 的根节点// 注意只有每个连通分量的根节点的 size[] 才可以代表该连通分量中的节点数int p uf.find(i);// 已经加入 list 的节点直接跳过if (!set.contains(p)) list.add(size[p]);set.add(p);}long ans 0;// 计算结果for (int sz : list) ans (long) sz * (n - sz);// 注意 ➗ 2return ans / 2;}
}
/* ------------ 并查集模版 ------------ */
class UF {private int count;private int[] parent;private int[] size;public UF(int n) {this.count n;parent new int[n];size new int[n];for (int i 0; i n; i) {parent[i] i;size[i] 1;}}public void union(int p, int q) {int rootP find(p);int rootQ find(q);if (rootP rootQ) return ;// 平衡性优化if (size[rootP] size[rootQ]) {parent[rootP] rootQ;size[rootQ] size[rootP];} else {parent[rootQ] rootP;size[rootP] size[rootQ];}this.count--;}public boolean connected(int p, int q) {int rootP find(p);int rootQ find(q);return rootP rootQ;}public int count() {return this.count;}// 增加了一个函数// 返回 size[]public int[] size() {return this.size;}public int find(int x) {// 路径压缩if (parent[x] ! x) {parent[x] find(parent[x]);}return parent[x];}
} 后言
上面是力扣图论专题下一篇是其他的习题希望有所帮助一同进步共勉
