剑指 Offer II 116. 省份数量-空间复杂度O（n），时间复杂度O(n)

剑指 Offer II 116. 省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

代如如下，简便递归法

void  f2(int** isConnected, int n,int *r,int j){
    
    int i;
    r[j]=0;
    for(i=0;i<n;i++){
    
        if(isConnected[j][i]==1&&r[i]==1&&i!=j){
    
            r[i]=0;
            f2(isConnected,n,r,i);

        }

    }
}

void  f(int** isConnected, int n,int *r,int *sum){
    
    int i,j;
    
    for(i=0;i<n;i++){
    
       
        if(r[i]==1){
    
        r[i]=0;
    
        (*sum)++;
         for(j=0;j<n;j++){
    
            
            if(isConnected[i][j]==1&&r[j]==1&&i!=j){
    
                f2(isConnected,n,r,j);
            }
        }
    }
    }
    
    

}



int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize){
    
   int n=isConnectedSize;
   int *sum=(int *)malloc(sizeof(int));
    int r[isConnectedSize];
    int i;
     for(i=0;i<n;i++){
    
       r[i]=1;
        }
    *sum=0;
    f(isConnected,n,r,sum);
    return *sum;

}