[Day8] 2022-02-25 - 547. 省份数量

题目

java

class Solution {
    public int findCircleNum(int[][] isConnected) {
        // int[][] isConnected 是无向图的邻接矩阵，n 为无向图的顶点数量
        int n = isConnected.length;
        // 定义 boolean 数组标识顶点是否被访问
        boolean[] visited = new boolean[n];
        // 定义 cnt 来累计遍历过的连通域的数量
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            // 若当前顶点 i 未被访问，说明又是一个新的连通域，则遍历新的连通域且cnt+=1.
            if (!visited[i]) { 
                cnt++;
                dfs(i, isConnected, visited);
            }
        }
        return cnt;
    }

    private void dfs(int i, int[][] isConnected, boolean[] visited) {
        // 对当前顶点 i 进行访问标记
        visited[i] = true;
        
        // 继续遍历与顶点 i 相邻的顶点（使用 visited 数组防止重复访问）
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                dfs(j, isConnected, visited);
            }
        }
    }
}

c++代码

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {

        int count =0; //最坏结果 n
        int rows = isConnected.size();//rows ==cols
        vector<bool> visited(rows,false); //直接相连

        for( int i =0;i<rows;i++)
        {
            if( visited[i] ==false)
            {
                dfs(i,isConnected,visited);
                count++;
            }
        }

        return count;
    }

    void dfs(int i,vector<vector<int>>& isConnected,vector<bool>& visited)
    {
        visited[i] = true;

        for(int j =0;j<isConnected.size();j++)
        { //isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连
            if (isConnected[i][j] ==1 && visited[j] ==false )
            {
                //a[0][0]
                dfs(j,isConnected,visited);
            }
        }
    }


};

golang

func findCircleNum(isConnected [][]int) int {

    rows :=len(isConnected)
    //https://www.cnblogs.com/sparkdev/p/10704614.html
    visited :=make([]bool,rows); //n 个城市，
    count :=0
    /////// 这些写阅读不方便，但是节省2个参数传递
    var dfs func(k int)
 dfs = func(k int) {
        visited[k] = true 
  for i := range isConnected[k] {
   c := isConnected[k][i]
   if c == 0 || visited[i] {
    continue
   }
   dfs(i)
  }
 }
    ////////

    for i:=0;i<rows;i++{
        if visited[i]!=true{
          count++
          dfs(i)
        }
    }

    return count
}