Union-Find solution within 1ms(I'm not sure anything wrong with the online judge)


  • 1
    X

    Using part of the union find algorithm. Order(n), linear space complexity. The OJ said beat 100% solution.I 've no idea is there anything wrong. Here is my code:

    public class Solution {
    public boolean canFinish(int n, int[][] p) {
        int[] g = new int[n];
        for(int i=0; i<n; i++)  g[i] = -1;
        for(int i=0; i<p.length; i++) {
            int curIndex = p[i][0];
            int rootIndex = p[i][1];
            g[curIndex] = rootIndex;
            while(g[rootIndex] != -1) {
                if(g[rootIndex] == curIndex) return false;
                g[curIndex] = g[rootIndex];
                rootIndex = g[rootIndex];
            }
        }
        return true;
    }
    

    }


  • 1
    X

    I've found this solution is wrong. Turns out the online judge hasn't consider one of the corner cases that one course requires two prerequisites courses


  • 0
    X

    I think Union-Find solution can not work properly for directed maps.


Log in to reply
 

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