---
title: 547. Number of Provinces
tags: leetcode,解題報告
---
{%hackmd @hlc23/dark-theme %}
# 547. Number of Provinces
題目連結: [Leetcode](https://leetcode.com/problems/number-of-provinces/description/)

## 題目概要
圖論題
給$n\times n$的陣列表各節點的相連情形
找出森林中樹的數量

## 想法
歷遍所有樹(DFS、BFS)

## 參考解法
歡迎補充
:::spoiler Python DFS解

class Solution:
    def dfs(self, node: int) -> None:
        self.visted[node] = True
        for i, status in enumerate(self.table[node]):
            if (status == 1 and self.visted[i] is False):
                self.dfs(i)

    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        self.n = len(isConnected)
        self.visted = [False for _ in range(len(isConnected))]
        self.table = isConnected

        ans = 0
        for i in range(self.n):
            if self.visted[i] is True:
                continue
            ans += 1
            self.dfs(i)
        
        return ans

:::
:::spoiler CPP DFS 解

class Solution {
public:
    int n;
    vector<bool> visted;

    void dfs(int node, vector<vector<int>> &table){
        visted[node] = true;
        for (int i=0; i<n; i++){
            if (!visted[i] and table[node][i] == 1) dfs(i, table);
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        n = isConnected.size();
        visted.resize(n, false);
        int ans = 0;
        for (int i=0; i<n; i++){
            if (!visted[i]){
                ans += 1;
                dfs(i, isConnected);
            }
        }
        return ans;
    }
};

:::