We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]] 输出:2
输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出:3
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/number-of-provinces 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
The text was updated successfully, but these errors were encountered:
一共有n个城市,每个城市和其它城市关联,那么就设置这个城市对应的value值设置为关联城市的索引。
func findCircleNum(isConnected [][]int) int { // 初始化所有集合 city := make([]int, len(isConnected)) for i := 0; i < len(isConnected); i++ { city[i] = i } // 并查集 find := func (x int) int { for city[x] != x{ x = city[x] } return x } union := func(x, y int) { city[x] = y } for i := 0; i < len(isConnected); i++ { for j := 0; j < len(isConnected[i]); j++ { if i == j { continue } if isConnected[i][j] == 1 { union(find(i), find(j)) } } } m := map[int]struct{}{} for i, _ := range city { p := find(i) if _, e := m[p]; !e { m[p] = struct{}{} } } return len(m) }
Sorry, something went wrong.
No branches or pull requests
有 n 个城市,其中一些彼此相连,另一些没有相连。如果城市 a 与城市 b 直接相连,且城市 b 与城市 c 直接相连,那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ,其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连,而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1:
示例 2:
提示:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-provinces
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
The text was updated successfully, but these errors were encountered: