C solution dfs and union find


  • 0
    S

    dfs:

    void dfs(int **M, int size, int *flags, int index)
    {
    	int i;
    	for(i=0; i<size; i++)
    	{
    		if(M[index][i]==0 || flags[i] == 1)	continue;
    		flags[i] = 1;
    		dfs(M, size, flags, i);
    	}
    }
    
    int findCircleNum(int** M, int MRowSize, int MColSize) {
    	int i, j, num=0;
    	int *flags = calloc(MRowSize, sizeof(int));
    	for(i=0; i<MRowSize; i++)
    	{
    		if(flags[i]) continue;
    		
    		flags[i] = 1;
    		dfs(M, MColSize, flags, i);
    		
    		num ++;
    	}
    
    	free(flags);
    	return num;
    }
    

    union find:

    int findRoot(int *flags, int index)
    {
    	if(flags[index] < 0)	return index;
    	flags[index] = findRoot(flags, flags[index]);
    
    	return flags[index];
    }
    
    //union find
    int findCircleNum(int **M, int MRowSize, int MColSize)
    {
    	int *flags = malloc(MRowSize*sizeof(int));
    	int i,j, num=MRowSize, l, r;
    
    	for(i=0;i<MRowSize;i++)
    	{
    		flags[i] = -1;
    	}
    	for(i=0; i<MRowSize; i++)
    	{
    		for(j=i+1; j<MColSize; j++)
    		{
    			if(M[i][j] == 0)	continue;
    			l = findRoot(flags, i);
    			r = findRoot(flags, j);
    			if(l == r)	continue;
    			if(l < r)
    			{
    				flags[r] = l;
    				flags[l] --;
    			}else{
    				flags[l] = r;
    				flags[r] --;
    			}
    			num--;
    		}
    	}
    
    	free(flags);
    	
    	return num;
    }
    

Log in to reply
 

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