Graph Connectivity With Threshold LeetCode solution in Java

1
// Solving the problem using Disjoint Set Union Find approach
2

3
class Solution {
4

5
  public int find(int x) {
6

7
    if (parent[x] == x) return x;
8

9
    // Optimising by placing the same parent for all the elements to reduce reduntant calls
10
    return parent[x] = find(parent[x]);
11
  }
12

13
  public void union(int a, int b) {
14

15
    a = find(a);
16
    b = find(b);
17

18
    // Using Rank optimisation
19
    if (rank[a] > rank[b]) {
20
      parent[b] = a;
21
      rank[a] += rank[b];
22
    } else {
23
      parent[a] = b;
24
      rank[b] += rank[a];
25
    }
26

27
    // parent[b] = a;
28
  }
29

30
  int parent[];
31
  int rank[];
32

33
  public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
34

35
    List<Boolean> ans = new ArrayList<Boolean>();
36
    parent = new int[n + 1];
37
    rank = new int[n + 1];
38

39
    for (int i = 1; i <= n; i++) {
40
      // Each element is its own parent
41
      parent[i] = i;
42
      // At beginning each element has rank 1
43
      rank[i] = 1;
44
    }
45

46
    // Finding the possible divisors with pairs above given threshold
47
    for (int th = threshold + 1; th <= n; th++) {
48

49
      int mul = 1;
50
      while (mul * th <= n) {
51
        // If possible pair then making a union of those paired element
52
        union(th, mul * th);
53
        mul++;
54
      }
55
    }
56

57
    // Generating ans for all possible queries
58
    for (int[] query : queries) {
59
      ans.add((find(query[0]) == find(query[1])));
60
    }
61
    return ans;
62
  }
63
}