547.Number-of-Provinces

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;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (visited[i] == false) {
                visited[i] = true;
                queue.add(i);
                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) {
                            queue.add(j);
                        }
                    }
                }
                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;
        } 
    }

}