2316. 统计无向图中无法互相到达点对数

本文主要是介绍2316. 统计无向图中无法互相到达点对数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

请你返回 无法互相到达 的不同 点对数目 。

---

  时间复杂度：O(N)
  思路：记录每个几点后续节点，vis记录节点是否已经被访问。使用DFS，记录每个未被访问的点，隐形上就进行了分簇。total记录所有已被遍历的点，size记录簇的大小。则res = res + size*total。

class Solution {public long countPairs(int n, int[][] edges) {List<Integer>[] g = new ArrayList[n];Arrays.setAll(g, e->new ArrayList());boolean[] vis = new boolean[n];for(int[] e:edges) {int x = e[0];int y = e[1];g[x].add(y);g[y].add(x);}long total = 0;long res = 0;for(int i=0; i<n; i++) {if(vis[i] == false) {int size = dfs(i, g, vis);res = res + total*size;total = total + size;}}return res;}private int dfs(int x, List<Integer>[] g, boolean[] vis) {int size = 1;vis[x] = true;for(int y:g[x]) {if(vis[y] == false) {size += dfs(y, g, vis);}}return size;}
}

这篇关于2316. 统计无向图中无法互相到达点对数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---