Java,Warshall


  • 0
    C

    The basic idea is to use the warshall algorithm to calculate the closure of a set.
    warshall is an o(n^3) algorithm to get the ring of a graph.

    int i, j, k;
    
    //warshall 
    for (i = 0; i < M.length; i++) {
    	for (j = 0; j < M.length; j++) {
    		for (k = 0; k < M.length; k++) {
    			if (M[j][i] != 0)
    				M[j][k] = M[j][k] + M[i][k];
    			if (M[j][k] != 0)
    				M[j][k] = 1;
    		}
    	}
    }
    
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    int total = 0;
    
    for (i = 0; i < M.length; i++) {
    	if (map.containsKey(i)) {// the key that has been explored
    		continue;
    	} else {// the key that has not been explored
    		for (j = 0; j < M.length; j++) {
    			if (M[i][j] == 1) {
    				if (!map.containsKey(j)) {// if the key doesn't exist,save it
    					map.put(j, 1);
    				}
    			}
    
    		}
    		total++;//everytime you calculate a row,total plus one
    	}
    
    }
    
    return total;
    
    

Log in to reply
 

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