本文主要是介绍LeetCode:547. 省份数量(并查集 Java),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
547. 省份数量
题目描述:
实现代码与解析:
原理思路:
547. 省份数量
题目描述:
有 n
个城市,其中一些彼此相连,另一些没有相连。如果城市 a
与城市 b
直接相连,且城市 b
与城市 c
直接相连,那么城市 a
与城市 c
间接相连。
省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个 n x n
的矩阵 isConnected
,其中 isConnected[i][j] = 1
表示第 i
个城市和第 j
个城市直接相连,而 isConnected[i][j] = 0
表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1:
输入:isConnected = [[1,1,0],[1,1,0],[0,0,1]] 输出:2
示例 2:
输入:isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出:3
提示:
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j]
为1
或0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
实现代码与解析:
import java.util.HashSet;
import java.util.Set;class Solution {int[] p = new int[210];public int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];}public int findCircleNum(int[][] isConnected) {int n = isConnected.length;int m = isConnected[0].length;// 初始化for (int i = 0; i < p.length; i++) {p[i] = i;}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (isConnected[i][j] == 1 && i != j) {p[find(i)] = find(j);}}}HashSet<Integer> set = new HashSet<>();for (int i = 0; i < n; i++) {set.add(find(i));}return set.size();}
}
原理思路:
简单的利用并查集而已。
原理请看我之前写的并查集详解。
Leetcode:684. 冗余连接(并查集C++)_树可以看成是一个连通且无环的无向图。 给定往一棵 n 个节点 (节点值 1~n) 的树-CSDN博客
然后注意这题,求的返回求根的种类即可,我这里用的set去重。over。
这篇关于LeetCode:547. 省份数量(并查集 Java)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!