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

题目描述：

给你一个整数 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
不会有重复边。

思路:

时间复杂度：O(n),空间复杂度O()

find函数就可以实现union

代码:

func countPairs(n int, edges [][]int) int64 {
    p := make([]int, n)
    cnt := make([]int,n)
    var res int64
    for i:=1;i<n;i++{
        p[i] = i
    }
    var find func(x int)int
    find = func(x int)int{
        if p[x] != x{
            p[x] = find(p[x])
        }
        return p[x]
    }

    m := len(edges)
    for i:=0;i<m;i++{
        if edges[i][0] > edges[i][1]{
            edges[i][0],edges[i][1] = edges[i][1],edges[i][0]
        }
        x,y := find(edges[i][0]),find(edges[i][1])
        p[x] = y
    }
    for i:=0;i<n;i++{
        cnt[find(p[i])] ++
    }
    sum := 0
    for i:=0;i<n;i++{
        if p[i] == i{
            res += int64(sum*cnt[i])
            sum += cnt[i]
        }
    }
    return res

}

代码效率：

执行用时：244 ms, 在所有 Go 提交中击败了92.86%的用户
内存消耗：23.6 MB, 在所有 Go 提交中击败了78.06%的用户