Problem
There 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]
Solution
解這題的想法是,將相連的點分成一群。
第一個想到方法是,我們可以利用 Union Find 來將點做分群。
第二個想到的方法是,對於任一個點,我們可以用 DFS 或 BFS 來所有找出相連的點,而這些點就會成一個群。然後,再對任一還沒被分群的點,做上述的動作,一直到所有的點都被分群。
Union Find
- Time:
- Space:
class Solution { class UnionFind { private int[] parents; private int count; UnionFind(int size) { count = size; parents = new int[size]; for (int i = 0; i < size; i++) { parents[i] = i; } } int find(int x) { while (x != parents[x]) { x = parents[x]; parents[x] = parents[parents[x]]; } return x; } void union(int x, int y) { int parentX = find(x); int parentY = find(y); if (parentX == parentY) { return; } else if (parentX < parentY) { parents[parentY] = parentX; } else { parents[parentX] = parentY; } count--; } int getCount() { return count; } } public int findCircleNum(int[][] isConnected) { int n = isConnected.length; UnionFind uf = new UnionFind(n); for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (i == j) continue; if (isConnected[i][j] == 1) { uf.union(i, j); } } } return uf.getCount(); } }
DFS
- Time:
- Space:
class Solution { public int findCircleNum(int[][] isConnected) { int count = 0; boolean[] isVisited = new boolean[isConnected.length]; for (int i = 0; i < isConnected.length; i++) { if (!isVisited[i]) { dfs(isConnected, i, isVisited); count++; } } return count; } private void dfs(int[][] isConnected, int i, boolean[] isVisited) { isVisited[i] = true; for (int j = 0; j < isConnected.length; j++) { if (isConnected[i][j] == 1 && !isVisited[j]) { dfs(isConnected, j, isVisited); } } } }
BFS
- Time:
- Space:
class Solution { public int findCircleNum(int[][] isConnected) { int count = 0; boolean[] isVisited = new boolean[isConnected.length]; for (int i = 0; i < isConnected.length; i++) { if (!isVisited[i]) { bfs(isConnected, i, isVisited); count++; } } return count; } private void bfs(int[][] isConnected, int i, boolean[] isVisited) { Queue<Integer> queue = new ArrayDeque<>(); queue.offer(i); while (!queue.isEmpty()) { int v = queue.poll(); if (isVisited[v]) continue; isVisited[v] = true; for (int j = 0; j < isConnected.length; j++) { if (isConnected[v][j] == 1 && !isVisited[j]) { queue.offer(j); } } } } }
參考
- 547. Number of Provinces, LeetCode.
- 547. Number of Provinces, LeetCode Solutions.