C++, Union Find


  • 0
    K

    The key point is applying Union Find here.

    int getFC(vector< vector<int> > &M){
    	  int size;
          size = fc_cnt = M.size();  
          int i, j;
    	  for(i =0 ; i < size - 1; i++){
    		  for(j = i + 1; j < size; j++){
              if(M[i][j] == 1){
                  union_node(i, j);
    		  }
    		 }
    	  }
    	  return fc_cnt;
    	}
    
    	int getRoot(int i){//获取节点i的根节点
    		while(p[i] != i){
    	      p[i] = p[p[i]];//让父节点修改为爷爷节点
              i = p[i];
    		}
    		return i;
    	}
    
        void union_node(int i, int j){
          int r1 = getRoot(i);
    	  int r2 = getRoot(j);
    	  if(r1 == r2) return;//同根则无须操作
    	  if(sizes[r1] > sizes[r2]){
              p[r2] = r1;
    		  sizes[r1] += sizes[r2];
    	  }
    	  else{
              p[r1] = r2;
    		  sizes[r2] += sizes[r1];
    	  }
    	  fc_cnt--;
    	}
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.