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

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

• 难度: medium
• 原始链接: https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph
• 标签: 深度优先遍历

解法一: 深度优先遍历

go

func countPairs(n int, edges [][]int) int64 {
    grip := make([][]int, n)
    for i := 0; i < n; i++ {
        grip[i] = []int{}
    }
    for _, edge := range edges {
        grip[edge[0]] = append(grip[edge[0]], edge[1])
        grip[edge[1]] = append(grip[edge[1]], edge[0])
    }
    visit := make([]bool, n)
    var ans int64
    var total int64
    for i := 0; i < n; i++ {
        size := dfs(i, grip, visit)
        ans += size * total
        total += size
    }
    return ans
}

func dfs(num int, grip [][]int, visit []bool) int64 {
    if visit[num] {
        return 0
    }
    visit[num] = true
    var size int64 = 1
    for _, num2 := range grip[num] {
        size += dfs(num2, grip, visit)
    }
    return size
}