# 547.Number-of-Provinces

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/number-of-provinces/

## ้ข็ฎๆ่ฟฐ

``````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] is 1 or 0.
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]``````

## ไปฃ็ 

### Approach #1 DFS

Time: O(N^2) && Space: O(N)

``````class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
int nums = 0;
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (visited[i] == false) {
dfs(isConnected, visited, i);
nums++;
}
}

return nums;
}

private void dfs(int[][] isConnected, boolean[] visited, int i) {
int n = isConnected.length;
for (int j = 0; j < n; j++) {
if (visited[j] == false && isConnected[i][j] == 1) {
visited[j] = true;
dfs(isConnected, visited, i);
}
}
}
}``````

### Approach #2 BFS

Time: O(N^2) && Space: O(N)

``````class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
int nums = 0;
boolean[] visited = new boolean[n];
for (int i = 0; i < n; i++) {
if (visited[i] == false) {
visited[i] = true;
while (!queue.isEmpty()) {
int s = queue.poll();
visited[s] = true;
for (int j = 0; j < n; j++) {
if (isConnected[s][j] == 1 && visited[j] == false) {
}
}
}
nums++;
}
}

return nums;
}
}``````

### Approach #3 Union Find

Time: O(N^3) && Space: O(N)

``````class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
int[] parent = new int[n];

for (int i = 0; i < n; i++) {
parent[i] = i;
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (isConnected[i][j] == 1 && i != j) {
union(parent, i, j);
}
}
}

int count = 0;
for (int i = 0; i < n; i++) {
if (parent[i] == i) {
count++;
}
}

return count;
}

private int find(int[] parent, int i) {
if (parent[i] == i) {
return i;
} else {
return find(parent, parent[i]);
}
}

private void union(int[] parent, int i, int j) {
int p1 = find(parent, i);
int p2 = find(parent, j);
if (p1 != p2) {
parent[p1] = p2;
}
}

}``````

Last updated