# 547. Number of Provinces

547\. 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:**

![](https://assets.leetcode.com/uploads/2020/12/24/graph1.jpg)

<pre><code><strong>Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
</strong><strong>Output: 2
</strong></code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/12/24/graph2.jpg)

<pre><code><strong>Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
</strong><strong>Output: 3
</strong></code></pre>

**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]`

***My Solutions:***

这道题和number of islands不一样。 matrix\[i]\[j]=1 代表i和j城市是相连的，他们在同一个省。求有多少个省。

方法1：DFS

遍历每个人，如果这个人之前没有访问过，说明有多一个新的朋友圈，答案记录加1。就从这个点作为起点做一次DFS，找出所有的直接朋友与间接朋友，并把他们标记访问。

Space: 一共最多N个人，每个人递归一次,所以递归空间是O(N), 标记数组visited也是O(N)。

Time：每个人递归一次，时间O(N)；递归时候会遍历他的所有朋友，遍历朋友是O(N)。 总复杂度O(N^2)

```
public int findCircleNum(int[][] matrix) {
    int count = 0, n = matrix.length;
    boolean[] visited = new boolean[n]; //标记是否已经检查过这个i
    for (int i = 0; i < matrix.length; i++) {
        // 如果我们已经检查过i，说明这个i和别的地方是连着的，不需要继续
        if (visited[i]) continue; 

        // 发现一个新的城市/省，把它周围的所有邻居都标记上
        count++;
        dfs(matrix, visited, i);
    }
    return count;
}


private void dfs(int[][] matrix, boolean[] visited, int i) {
    visited[i] = true; // 标记这个i已经被访问过了
    for (int j = 0; j < matrix.length; j++) {
        if (i == j || visited[j] || matrix[i][j] == 0) continue;
        dfs(matrix, visited, j);
    }
}
```

方法2：BFS

* 遍历每个人，如果这个人之前没有访问过，说明有多一个新的朋友圈，答案记录加1。就从这个点作为起点做一次BFS，找出所有的直接朋友与间接朋友，并把他们标记访问。
* BFS流程
  * 将起点压入队列，标记访问
  * 取出队首，从队首向外找朋友，看都能扩展到哪些还没访问的朋友，压入队列并标记访问
  * 重复执行上一步，直到队列为空

时间和空间复杂度和方法1一样

```
public int findCircleNum(int[][] matrix) {
    int count = 0, n = matrix.length;
    boolean[] visited = new boolean[n];
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        q.offer(i);
        while (!q.isEmpty()) {
            int j = q.poll();
            visited[j] = true;
            for (int k = 0; k < n; k++) {
                if (matrix[j][k] == 1 && !visited[k]) q.offer(k);
            }
        }
        count++;
    }
    return count;
}
```

方法3：用disjointed set/union find&#x20;

以下是用union find的模版

<pre><code><strong>class Solution {
</strong>    // Union Find
    public int findCircleNum(int[][] isConnected) {
        if (isConnected == null || isConnected.length == 0) {
            return 0;
        }

        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i &#x3C; n; i++) {
            for (int j = 0; j &#x3C; n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }

        return uf.getCount();
    }

    class UnionFind {
        private int[] root;
        private int[] rank;
        private int count;

        UnionFind(int size) {
            root = new int[size];
            rank = new int[size];
            count = size;
            for (int i = 0; i &#x3C; size; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

        int find(int x) {
            if (x == root[x]) {
                return x;
            }
            return root[x] = find(root[x]);
        }

        void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                } else if (rank[rootX] &#x3C; rank[rootY]) {
                    root[rootX] = rootY;
                } else {
                    root[rootY] = rootX;
                    rank[rootX] += 1;
                }
                count--;
            }
        }

        int getCount() {
            return count;
        }
    }
}
</code></pre>

也可以简化一下

```
public int findCircleNum(int[][] matrix) {
    int count = 0, n = matrix.length;
    
    // 这是union find的setup
    int[] root = new int[n];
    for (int i = 0; i < n; i++) root[i] = i;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (matrix[i][j] == 1) union(root, i, j);
        }
    }

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

private void union(int[] root, int x, int y) {
    root[find(root, x)] = find(root, y);
}
private int find(int[] root, int x) {
    if (x == root[x]) return x;
    return root[x] = find(root, root[x]);
}
```
