Using Union Find but passing 33/37 test cases. Need Help


  • 0
    R
    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            int arr[] = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                arr[i] = i;
            }
            for (int i = 0; i < prerequisites.length; i++) {
                int x = prerequisites[i][0];
                int y = prerequisites[i][1];
                if (root(arr, x) == root(arr, y)) {
                    return false;
                }
                arr[x] = y;
            }
            return true;
        }
        public int root(int arr[], int i) {
            while (i != arr[i]) {
                arr[i] = arr[arr[i]];
                i = arr[i];
            }
            return i;
        }
    }
    

    Failing test case
    4
    [[1,0],[2,0],[3,1],[3,2]]
    Output - false;
    Expected - true;

    Can anyone please help me fix this?


  • 0
    I

    this is directed graph. Union Find detect cycle for undirected graph.
    for directed graph. connected doesn't mean cycle.


  • 0
    R

    @iroot900 Thanks. It makes more sense now.


Log in to reply
 

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