图论1(Leetcode547.省份数量)

答案：

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        int[] arr = new int[n];
        int ans = 0;

        for(int i=0;i<n;i++){
            if(arr[i]==0){
                ans++;
                arr[i] = 1;
                while(findCity(arr,isConnected[i])!=-1){
                    addCity(arr,isConnected, i);
                }
            }
        }
        return ans;
    }
    public int findCity(int[] arr,int[] isConnectedI){
        //判断有没有新增元素
        for(int i=0;i<arr.length;i++){
            if(isConnectedI[i]==1&&arr[i]==0){
                //有新增返回新增坐标
                return i;
            }
        }
        //无新增返回0
        return -1;
    }
    public int[] addCity(int[]arr, int[][] isConnected, int city){
        //在省份中加入没有加入的城市
        int x;
        while((x = findCity(arr,isConnected[city]))!=-1){
            arr[x] = 1;
            addCity(arr, isConnected, x);
        }
        
        return arr;
    }

}