Friday, May 8, 2015

Good Node Google Interview Question

Union Find Algorithm
Check this link
https://www.cs.duke.edu/courses/cps100e/current/rodger/lects/110317/wayne/15UnionFindMod.ppt

public static int find(int[] parent, int x) {
if (x==0) return 0;
if (parent[x] == -1 || parent[x] == x) return x;
return find(parent, parent[x]);
}

public static void union(int[] parent, int x, int y) {
int xp = find(parent, x);
int yp = find(parent, y);
parent[xp] = yp;
}

public static int minChanges(int[] A) {
int n=A.length;
int[] parent = new int[n];//parent contains the id for quick find
Arrays.fill(parent, -1);
for (int i=0; i<n; i++) {
union(parent, i, A[i]);
}

int count = 0;
for (int i=1; i<n; i++) {
if (find(parent,i) == i) {
count++;
}
}
return count;
}

public static void main(String args[] ) throws Exception {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[] A = new int[n];
        for(int i=0; i<n; i++) {
            A[i] = s.nextInt()-1;
        }
        System.out.print(Arrays.toString(A));
        s.close();
        System.out.println(minChanges(A));
    }

No comments:

Post a Comment