0

I am trying to understand this implementation of quick find , but stuck at one line of code.that is : max[qId] = max[pId] > max[pId] ? max[pId] : max[qId]

To my understanding max[qid] is assigned max[pid] but why again this: "> max[pId]".

this is the question: Union-find with the specific canonical element. Add a method () to the union-find data type so that () returns the largest element in the connected component containing ii. The operations, (), (), and () should all take the logarithmic time or better.

For example, if one of the connected components is {1, 2, 6, 9}{1,2,6,9}, then the () method should return 99 for each of the four elements in the connected components.

This is the code.

''' package sec1.Exercise;

public class UF {

private int[] id;   //Component id
private int[] sz;   //The magnitude of the component corresponding to each root node
private int count;  //Component quantity
private int[] max;

public UF(int N){
    count = N;
    id = new int[N];
    sz = new int[N];
    max = new int[N];
    for(int i = 0;i < N;i++){
        id[i] = i;
        sz[i] = 1;
        max[i] = i;
    }

}

public int count(){
    return count;
}

public boolean connected(int p,int q){
    return find(p) == find(q);
}

private int find(int i){
    while (id[i] != i){
        i = id[i];
    }
    return i;
}

public void union(int p,int q){
    int pId = find(p);
    int qId = find(q);

    if(pId == qId){
        return;
    }
    if(sz[pId] < sz[qId]){
        id[pId] = qId;
        sz[qId] += sz[pId];
        max[qId] = max[pId] > max[pId] ? max[pId] : max[qId];
    }else{
        id[qId] = pId;
        sz[pId] += sz[qId];
        max[pId] = max[pId] > max[qId] ? max[pId] : max [qId];
    }
    count--;
}

public int getMax(int i){
    return max[find(i)];
}

} '''

Rishit Dagli
  • 1,000
  • 8
  • 20
nitin gaur
  • 1
  • 2
  • This seems to be a typo. I guess the line should be `max[qId] = max[pId] > max[qId] ? max[pId] : max [qId];` – Henry Jul 11 '20 at 07:11
  • Can you please explain this , as I am not able to understand that whole line of code. – nitin gaur Jul 11 '20 at 07:24
  • `max[pId] > max[qId] ? max[pId] : max [qId]` gives the maximum of `max[pId]` and `max[qId]`. This is then assigned to `max[qId]`. – Henry Jul 11 '20 at 07:26
  • you mean for example ,let max[pid]=2 and max[qid]=3, then 2>3?2:3, this whole gives 3 .right? also can you please explain why we use this- ":" . thanks. – nitin gaur Jul 11 '20 at 08:23
  • Because that's the syntax for the ternary operator. See the question attached as a duplicate. – Henry Jul 11 '20 at 08:26
  • thank you,the attached question completely clarified my doubt. – nitin gaur Jul 11 '20 at 08:35

0 Answers0