547. Number of Provinces

https://leetcode.com/problems/number-of-provinces/

Problem

Intuition

Approach

• Các node liên kết với nhau tạo thành 1 province
• Dùng DFS để duyệt các node liên kết với nhau và mark các node đã visit

Implementation

class Solution {
    private int[][] isConnected;
    private int n;
    private boolean[] visited;

    public int findCircleNum(int[][] isConnected) {
        this.isConnected = isConnected;
        this.n = isConnected.length;
        this.visited = new boolean[n];
        int ans = 0;
        
        for (int city = 0; city < n; city++) {
            if (visited[city]) continue;
            dfs(city);
            ans++;
        }

        return ans;
    }

    private void dfs(int city) {
        if (visited[city]) return;
        visited[city] = true;

        for (int anotherCity = 0; anotherCity < n; anotherCity++) {
            if (visited[anotherCity]) continue;
            if (isConnected[city][anotherCity] != 1) continue;
            dfs(anotherCity);
        }
    }
}