Sword finger offer II 116 Number of provinces - spatial complexity O (n), time complexity O (n)

The finger of the sword Offer II 116. Number of provinces

Yes n Cities , Some of them are connected to each other , Others are not connected . If the city a And the city b Direct connection , And the city b And the city c Direct connection , So the city a And the city c Indirectly connected .

Province It's a group of directly or indirectly connected cities , There are no other cities in the group that are not connected .

To give you one n x n Matrix isConnected , among isConnected[i][j] = 1 It means the first one i Two cities and j The two cities are directly connected , and isConnected[i][j] = 0 The two are not directly connected .

Back in the matrix Province The number of .

Example 1：

Input ：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output ：2

Example 2：

Input ：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
Output ：3

As follows: , Simple recursive method

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;

}