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:

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]

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

以下是用union find的模版

class Solution {
    // 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 < n; i++) {
            for (int j = 0; j < 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 < 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] < rank[rootY]) {
                    root[rootX] = rootY;
                } else {
                    root[rootY] = rootX;
                    rank[rootX] += 1;
                }
                count--;
            }
        }

        int getCount() {
            return count;
        }
    }
}

也可以简化一下

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]);
}