547.Number of Provinces

tags: Medium,Graph,DFS,BFS,Union Find

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 i^th city and the j^th 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]

解答

C++

class DisjointSet {
public:
    vector<int> parent;
    vector<int> size;
    int count;

    DisjointSet(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i ++) {
            parent[i] = i;
        }
        count = n;
    }
    int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }
    bool isConnected(int p, int q) {
        return find(p) == find(q);
    }
    void union_(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) {
            return ;
        }
        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
        count --;
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        ios_base::sync_with_stdio(0), cin.tie(0);
        const int CONNECTED = 1;
        int n = isConnected.size();
        if (n == 1) {
            return 1;
        }
        DisjointSet dset(n);
        for (int u = 0; u < n; u ++) {
            for (int v = 0; v < n; v ++) {
                if (isConnected[u][v] == CONNECTED) {
                    dset.union_(u, v);
                }
            }
        }
        return dset.count;
    }
};

Jerry Wu4 June, 2023

Python

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        ans = 0
        visited = set()

        def dfs(node):
            visited.add(node)
            for child, connect in enumerate(isConnected[node]):
                if connect and child not in visited:
                    dfs(child)
        
        for i in range(n):
            if i not in visited:
                dfs(i)
                ans += 1
        return ans

Yen-Chi ChenSun, Jun 4, 2023

C#

public int FindCircleNum(int[][] isConnected) {
    int size = isConnected.Length;
    bool[] visited = new bool[size];

    int provinces = 0;
    for (int i = 0; i < size; i++) {
        if (!visited[i]) {
            provinces++;
            DFS(i);
        } 
    }

    return provinces;

    void DFS(int index) {
        visited[index] = true;
        for (int i = 0; i < size; i++) {
            if (isConnected[index][i] == 1 && !visited[i]) {
                DFS(i);
            }
        }
    }
}

JimJun 6, 2023

Reference

回到題目列表