My solution By represent graph as a matrix


  • 0
    C
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    	int[][] matrix = new int[numCourses][numCourses];
    	for (int i = 0; i < prerequisites.length; i++) {
    		matrix[prerequisites[i][1]][prerequisites[i][0]] = 1;
    	}
    	int[] pointToMe = new int[numCourses];
    	boolean[] finished = new boolean[numCourses];
    	/* every node gets the # of nodes point to me */
    	for (int i = 0; i < numCourses; i++)
    		for (int j = 0; j < numCourses; j++)
    			if (matrix[i][j] > 0)	pointToMe[j]++;
    	int cnt = 0;
    	for (int i = 0; i < numCourses; i++) {
    		if (!finished[i] && pointToMe[i] == 0) {
    			finished[i] = true;
    			for (int j = 0; j < numCourses; j++) {
    				if (matrix[i][j] > 0)	pointToMe[j]--;
    			}
    			cnt++;
    			i = -1;
    		}
    	}
    	return cnt == numCourses;
    }

Log in to reply
 

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