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

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

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

示例 1：

**输入：** n = 3, edges = [[0,1],[0,2],[1,2]]
**输出：** 0
**解释：** 所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。

示例 2：

**输入：** n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
**输出：** 14
**解释：** 总共有 14 个点对互相无法到达：
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。

提示：

• 1 <= n <= 105
• 0 <= edges.length <= 2 * 105
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• 不会有重复边。

本题 视频讲解 已出炉，欢迎点赞三连~

---

建图后，用 DFS 可以求出每个连通块的大小。

求连通块的大小的同时，用一个变量 tot 维护前面求出的连通块的大小之和。设当前连通块的大小为 size，那么它对答案的贡献就是 size}\cdot\textit{tot。

累加所有贡献，即为答案。

[sol1-Python3]

class Solution:
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        vis, ans, tot, size = [False] * n, 0, 0, 0
        def dfs(x: int) -> None:
            nonlocal size
            vis[x] = True
            size += 1
            for y in g[x]:
                if not vis[y]:
                    dfs(y)
        for i in range(n):
            if not vis[i]:
                size = 0
                dfs(i)
                ans += size * tot
                tot += size
        return ans

[sol1-Java]

class Solution {
    List<Integer>[] g;
    boolean[] vis;
    int cnt;

    public long countPairs(int n, int[][] edges) {
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }
        vis = new boolean[n];
        var ans = 0L;
        for (int i = 0, tot = 0; i < n; ++i)
            if (!vis[i]) {
                cnt = 0;
                dfs(i);
                ans += (long) cnt * tot;
                tot += cnt;
            }
        return ans;
    }

    void dfs(int x) {
        vis[x] = true;
        ++cnt;
        for (var y : g[x]) if (!vis[y]) dfs(y);
    }
}

[sol1-C++]

class Solution {
public:
    long long countPairs(int n, vector<vector<int>> &edges) {
        vector<vector<int>> g(n);
        for (auto &e : edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        bool vis[n]; memset(vis, 0, sizeof(vis));
        long ans = 0L;
        int cnt = 0;
        function<void(int)> dfs = [&](int x) {
            vis[x] = true;
            ++cnt;
            for (int y: g[x]) if (!vis[y]) dfs(y);
        };
        for (int i = 0, tot = 0; i < n; ++i)
            if (!vis[i]) {
                cnt = 0;
                dfs(i);
                ans += (long) cnt * tot;
                tot += cnt;
            }
        return ans;
    }
};

[sol1-Go]

func countPairs(n int, edges [][]int) (ans int64) {
	g := make([][]int, n)
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}

	vis := make([]bool, n)
	tot, size := 0, 0
	var dfs func(int)
	dfs = func(x int) {
		vis[x] = true
		size++
		for _, y := range g[x] {
			if !vis[y] {
				dfs(y)
			}
		}
	}
	for i, b := range vis {
		if !b {
			size = 0
			dfs(i)
			ans += int64(size) * int64(tot)
			tot += size
		}
	}
	return
}