并查集(UnionFind) 系列
2021/11/21 6:09:51
本文主要是介绍并查集(UnionFind) 系列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
547. Number of Provinces
MediumThere are n
cities. Some of them are connected, while some are not. If city a
is connected directly with city b
, and city b
is connected directly with city c
, then city a
is connected indirectly with city c
.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n
matrix isConnected
where isConnected[i][j] = 1
if the ith
city and the jth
city are directly connected, and isConnected[i][j] = 0
otherwise.
Return the total number of provinces.
Example 1:
Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]] Output: 2
Example 2:
Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]] Output: 3
Constraints:
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j]
is1
or0
.isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
解法1: 并查集
class Solution { public int findCircleNum(int[][] isConnected) { //1.for loop len elements do unionfind UnionFind uf = new UnionFind(isConnected.length); for(int i=0;i<isConnected.length;i++){ for(int j=0;j<isConnected.length;j++){ if(i!=j && isConnected[i][j]==1) { uf.union(i,j); } } } //2.count the parent[i]=i int count = 0; for(int i=0;i<isConnected.length;i++) if(uf.parent[i]==i) count++; return count; } //UnionFind implementation class UnionFind{ int[] parent; int[] rank; UnionFind(int n){ parent = new int[n]; rank = new int[n]; for(int i=0;i<n;i++) parent[i]=i; } public int findParent(int x){ if(x==parent[x]) return x; parent[x] = findParent(parent[x]); return parent[x]; } public void union( int x,int y ){ int px = findParent(x); int py = findParent(y); if(px==py) return; if(rank[px]>rank[py]) parent[py]=px; else if(rank[px]<rank[py]) parent[px]=py; else{ parent[px]=py; rank[py]++; } } } }
解法二: dfs
class Solution { public int findCircleNum(int[][] isConnected) { //defind visited int len = isConnected.length; boolean[] visited = new boolean[len]; //for loop 0 ~ len-1 recursively find its connections int count = 0; for(int i=0;i<len;i++){ if(visited[i]) continue; count++; dfs(isConnected,i,visited); } return count; } private void dfs(int[][] isConnected,int i,boolean[] visited){ int len = isConnected.length; visited[i]=true; for(int j=0;j<len;j++){ if(isConnected[i][j]==1 && !visited[j] ) dfs(isConnected,j,visited); } } }
这篇关于并查集(UnionFind) 系列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求