1class UnionFind {
2    constructor(N: number) {
3        // Initialize with N objects (0 to N-1)
4    }
5
6    union(p: number, q: number): void {
7        // Add connection between p and q
8    }
9
10    connected(p: number, q: number): boolean {
11        // Are p and q in the same component?
12        return false;
13    }
14
15    find(p: number): number {
16        // Find the component identifier for p
17        return -1;
18    }
19
20    count(): number {
21        // Number of distinct components
22        return 0;
23    }
24}

1class UnionFind {
2    constructor(N: number) {
3        // Initialize with N objects (0 to N-1)
4    }
5
6    union(p: number, q: number): void {
7        // Add connection between p and q
8    }
9
10    connected(p: number, q: number): boolean {
11        // Are p and q in the same component?
12        return false;
13    }
14
15    find(p: number): number {
16        // Find the component identifier for p
17        return -1;
18    }
19
20    count(): number {
21        // Number of distinct components
22        return 0;
23    }
24}

1class QuickFind {
2
3  // interperation of the id array
4  // p and q are connected if they have the same id
5  private id: Array<number>;
6  private N: number;
7  private nComponents: number;
8
9  constructor(n: number) {
10    this.N = n;
11    this.nComponents = n;
12    this.id = new Array<number>(n).fill(0);
13
14    // each id or node is connected to only itself. so let them have same value as their id
15    this.id.forEach((_, index, array) => {
16      array[index] = index;
17    })
18  }
19
20  // every element that's in same component as p, will have same value in id array.
21  // find all such and change them to id of q node
22  // N operations everytime a union is performed.
23  public union(p: number, q: number): void {
24
25    if(this.connected(p,q)) {
26      return;
27    }
28
29    const idOfComponentContainingP = this.id[p];
30    const idOfComponentContainingQ = this.id[q];
31
32    this.id.forEach((_,index,array) => {
33      // if it belongs to component same as p
34      if(array[index] === idOfComponentContainingP) {
35        // change it to make it a part of component same as q
36        array[index] = idOfComponentContainingQ
37      }
38    })
39
40    this.nComponents -= 1;
41  }
42
43  // constant time operation every time connected is performed
44  public connected(p: number, q: number): boolean {
45    return this.id[p] === this.id[q];
46  }
47
48  // same as root(p: number): number
49  // every component has one id, lets call it it's root. 
50  public find(p: number): number {
51    return this.id[p]
52  }
53
54  public count(): number {
55    return this.nComponents;
56  }
57
58  public display(): void {
59    const n = this.id.length;
60    let result = "";
61    for (let i = 0; i < n; i++) {
62        result += `${this.id[i]} `;
63    }
64    console.log(`[${result}]`);
65  }
66}
67
68export {
69  QuickFind
70};

1class QuickFind {
2
3  // interperation of the id array
4  // p and q are connected if they have the same id
5  private id: Array<number>;
6  private N: number;
7  private nComponents: number;
8
9  constructor(n: number) {
10    this.N = n;
11    this.nComponents = n;
12    this.id = new Array<number>(n).fill(0);
13
14    // each id or node is connected to only itself. so let them have same value as their id
15    this.id.forEach((_, index, array) => {
16      array[index] = index;
17    })
18  }
19
20  // every element that's in same component as p, will have same value in id array.
21  // find all such and change them to id of q node
22  // N operations everytime a union is performed.
23  public union(p: number, q: number): void {
24
25    if(this.connected(p,q)) {
26      return;
27    }
28
29    const idOfComponentContainingP = this.id[p];
30    const idOfComponentContainingQ = this.id[q];
31
32    this.id.forEach((_,index,array) => {
33      // if it belongs to component same as p
34      if(array[index] === idOfComponentContainingP) {
35        // change it to make it a part of component same as q
36        array[index] = idOfComponentContainingQ
37      }
38    })
39
40    this.nComponents -= 1;
41  }
42
43  // constant time operation every time connected is performed
44  public connected(p: number, q: number): boolean {
45    return this.id[p] === this.id[q];
46  }
47
48  // same as root(p: number): number
49  // every component has one id, lets call it it's root. 
50  public find(p: number): number {
51    return this.id[p]
52  }
53
54  public count(): number {
55    return this.nComponents;
56  }
57
58  public display(): void {
59    const n = this.id.length;
60    let result = "";
61    for (let i = 0; i < n; i++) {
62        result += `${this.id[i]} `;
63    }
64    console.log(`[${result}]`);
65  }
66}
67
68export {
69  QuickFind
70};

1class QuickUnion {
2
3  // this array now represents a set of trees. each entry points to id of it's aprent in the array
4  // initially all are their own parent
5  private id: Array<number>;
6  private N: number;
7  private nComponents: number;
8
9  constructor(n: number) {
10    this.N = n;
11    this.nComponents = n;
12
13    this.id = new Array<number>(n).fill(0);
14    this.id.forEach((_, index, array) => {
15      // every element / node is their own parent hence storing value of their own id;
16      array[index] = index;
17    })
18  }
19
20  union(p: number, q: number): void {
21
22    if(this.connected(p,q)) {
23      return;
24    }
25
26    const rootP = this.find(p);
27    const rootQ = this.find(q);
28
29    this.id[rootP] = rootQ;
30    this.nComponents -= 1;
31  }
32
33  // this time same as checking if p and q have same root / same identifier for their component.
34  // earlier we were storing the identifier tiself in array, but now we are storing parent
35  // so new indirect identifier is the ROOT. keep going from parent to parent untill u cant
36  connected(p: number, q: number): boolean {
37    return this.find(p) === this.find(q);
38  }
39
40  // same as root(p: number): number
41  find(p: number): number {
42    let child = p;
43    let parent = this.id[p];
44
45    // in case we find root element, it's value will point to it's own id. 
46    // child is the element / id / node
47    // parent is the value of that id in array, id of another element. sighs
48    while(child !== parent) {
49      child = parent
50      parent = this.id[child]
51    }
52    return parent;
53  }
54
55  count(): number {
56    return this.nComponents;
57  }
58
59  public display(): void {
60    const n = this.id.length;
61    let result = "";
62    for (let i = 0; i < n; i++) {
63        result += `${this.id[i]} `;
64    }
65    console.log(`[${result}]`);
66  }
67}
68
69export { QuickUnion };

1class QuickUnion {
2
3  // this array now represents a set of trees. each entry points to id of it's aprent in the array
4  // initially all are their own parent
5  private id: Array<number>;
6  private N: number;
7  private nComponents: number;
8
9  constructor(n: number) {
10    this.N = n;
11    this.nComponents = n;
12
13    this.id = new Array<number>(n).fill(0);
14    this.id.forEach((_, index, array) => {
15      // every element / node is their own parent hence storing value of their own id;
16      array[index] = index;
17    })
18  }
19
20  union(p: number, q: number): void {
21
22    if(this.connected(p,q)) {
23      return;
24    }
25
26    const rootP = this.find(p);
27    const rootQ = this.find(q);
28
29    this.id[rootP] = rootQ;
30    this.nComponents -= 1;
31  }
32
33  // this time same as checking if p and q have same root / same identifier for their component.
34  // earlier we were storing the identifier tiself in array, but now we are storing parent
35  // so new indirect identifier is the ROOT. keep going from parent to parent untill u cant
36  connected(p: number, q: number): boolean {
37    return this.find(p) === this.find(q);
38  }
39
40  // same as root(p: number): number
41  find(p: number): number {
42    let child = p;
43    let parent = this.id[p];
44
45    // in case we find root element, it's value will point to it's own id. 
46    // child is the element / id / node
47    // parent is the value of that id in array, id of another element. sighs
48    while(child !== parent) {
49      child = parent
50      parent = this.id[child]
51    }
52    return parent;
53  }
54
55  count(): number {
56    return this.nComponents;
57  }
58
59  public display(): void {
60    const n = this.id.length;
61    let result = "";
62    for (let i = 0; i < n; i++) {
63        result += `${this.id[i]} `;
64    }
65    console.log(`[${result}]`);
66  }
67}
68
69export { QuickUnion };

1/*
2  Proposition: Depth of any node is at max Log(n), therefore
3  cost of finding roots is easier, in previous (quick union, this wasn't the case)
4*/
5
6// depth of any node here is at most log base 2 of N
7
8class WeightedQuickUnion {
9
10  private id: Array<number>;
11  private N: number;
12  private nComponents: number;
13  // keeps weight of tree with root at the item
14  // = number of items with root as the node INDEX
15  private weights: Array<number>;
16  // for visualisation, not required for this algorithm
17  // private tree: Map<number, Array<number>>;
18
19  /*
20    cost: n
21  */
22  constructor(n: number) {
23    this.N = n;
24    this.nComponents = n;
25
26    // not needed for this algorithm
27    // this.tree = new Map();
28
29    this.id = new Array<number>(n).fill(0);
30    this.id.forEach((_, index, array) => {
31      // every element / node is their own parent hence storing value of their own id;
32      array[index] = index;
33    })
34
35    // weight at node i is the number of elements that has it as it's root.
36    this.weights = new Array<number>(n).fill(1);
37  }
38
39  // same as root(p: number): number
40  find(p: number): number {
41    let child = p;
42    let parent = this.id[p];
43
44    // in case we find root element, it's value will point to it's own id. 
45    // child is the element / id / node
46    // parent is the value of that id in array, id of another element. sighs
47    while(child !== parent) {
48      child = parent
49      parent = this.id[child]
50    }
51    return parent;
52  }
53
54  // constant time operation every time connected is performed
55  public connected(p: number, q: number): boolean {
56    return this.find(p) === this.find(q);
57  }
58
59  /*
60    link root of smaller tree to root of larger tree
61  */
62  public union(p: number, q: number): void {
63
64    const rootP = this.find(p)
65    const rootQ = this.find(q)
66
67    if(rootP === rootQ) {
68      return;
69    }
70
71    // p is in smaller tree, make p's root's parent q's root
72    if(this.weights[rootP] < this.weights[rootQ]) {
73      this.id[rootP] = rootQ
74      this.weights[rootQ] = this.weights[rootQ] + this.weights[rootP];
75
76      // Update tree structure
77      // this.tree.has(rootQ) ? this.tree.get(rootQ)?.push(rootP) : this.tree.set(rootQ, [rootP])
78    } else {
79      this.id[rootQ] = rootP
80      this.weights[rootP] = this.weights[rootQ] + this.weights[rootP]
81
82      // Update tree structure
83      // this.tree.has(rootP) ? this.tree.get(rootP)?.push(rootQ) : this.tree.set(rootP, [rootQ])
84    }
85
86    this.nComponents -= 1;
87  }
88
89  count(): number {
90    return this.nComponents;
91  }
92
93  public display(): void {
94    const n = this.id.length;
95    let result = "";
96    for (let i = 0; i < n; i++) {
97        result += `${this.id[i]} `;
98    }
99    console.log(`[${result}]`);
100  }
101
102  public getData(): typeof this.id {
103    return this.id
104  }
105
106  public findComponent(p: number): Array<number> {
107    const rootP = this.find(p);
108    const component = [];
109
110    for (let i = 0; i < this.N; i++) {
111      if (this.find(i) === rootP) {
112        component.push(i);
113      }
114    }
115
116    return component;
117  }
118
119  // public getTree(): Map<number, Array<number>> {
120  //   return this.tree;
121  // }
122}
123
124export { WeightedQuickUnion };
125

1/*
2  Proposition: Depth of any node is at max Log(n), therefore
3  cost of finding roots is easier, in previous (quick union, this wasn't the case)
4*/
5
6// depth of any node here is at most log base 2 of N
7
8class WeightedQuickUnion {
9
10  private id: Array<number>;
11  private N: number;
12  private nComponents: number;
13  // keeps weight of tree with root at the item
14  // = number of items with root as the node INDEX
15  private weights: Array<number>;
16  // for visualisation, not required for this algorithm
17  // private tree: Map<number, Array<number>>;
18
19  /*
20    cost: n
21  */
22  constructor(n: number) {
23    this.N = n;
24    this.nComponents = n;
25
26    // not needed for this algorithm
27    // this.tree = new Map();
28
29    this.id = new Array<number>(n).fill(0);
30    this.id.forEach((_, index, array) => {
31      // every element / node is their own parent hence storing value of their own id;
32      array[index] = index;
33    })
34
35    // weight at node i is the number of elements that has it as it's root.
36    this.weights = new Array<number>(n).fill(1);
37  }
38
39  // same as root(p: number): number
40  find(p: number): number {
41    let child = p;
42    let parent = this.id[p];
43
44    // in case we find root element, it's value will point to it's own id. 
45    // child is the element / id / node
46    // parent is the value of that id in array, id of another element. sighs
47    while(child !== parent) {
48      child = parent
49      parent = this.id[child]
50    }
51    return parent;
52  }
53
54  // constant time operation every time connected is performed
55  public connected(p: number, q: number): boolean {
56    return this.find(p) === this.find(q);
57  }
58
59  /*
60    link root of smaller tree to root of larger tree
61  */
62  public union(p: number, q: number): void {
63
64    const rootP = this.find(p)
65    const rootQ = this.find(q)
66
67    if(rootP === rootQ) {
68      return;
69    }
70
71    // p is in smaller tree, make p's root's parent q's root
72    if(this.weights[rootP] < this.weights[rootQ]) {
73      this.id[rootP] = rootQ
74      this.weights[rootQ] = this.weights[rootQ] + this.weights[rootP];
75
76      // Update tree structure
77      // this.tree.has(rootQ) ? this.tree.get(rootQ)?.push(rootP) : this.tree.set(rootQ, [rootP])
78    } else {
79      this.id[rootQ] = rootP
80      this.weights[rootP] = this.weights[rootQ] + this.weights[rootP]
81
82      // Update tree structure
83      // this.tree.has(rootP) ? this.tree.get(rootP)?.push(rootQ) : this.tree.set(rootP, [rootQ])
84    }
85
86    this.nComponents -= 1;
87  }
88
89  count(): number {
90    return this.nComponents;
91  }
92
93  public display(): void {
94    const n = this.id.length;
95    let result = "";
96    for (let i = 0; i < n; i++) {
97        result += `${this.id[i]} `;
98    }
99    console.log(`[${result}]`);
100  }
101
102  public getData(): typeof this.id {
103    return this.id
104  }
105
106  public findComponent(p: number): Array<number> {
107    const rootP = this.find(p);
108    const component = [];
109
110    for (let i = 0; i < this.N; i++) {
111      if (this.find(i) === rootP) {
112        component.push(i);
113      }
114    }
115
116    return component;
117  }
118
119  // public getTree(): Map<number, Array<number>> {
120  //   return this.tree;
121  // }
122}
123
124export { WeightedQuickUnion };
125

1// same as root(p: number): number
2  find(p: number): number | null {
3
4    if(p < 0 || p >= this.N) {
5      return null
6    }
7
8    let child = p;
9    let parent = this.id[p];
10
11    // in case we find root element, it's value will point to it's own id. 
12    // child is the element / id / node
13    // parent is the value of that id in array, id of another element. sighs
14    while(child !== parent) {
15      child = parent
16      parent = this.id[child]
17    }
18
19    // apply path compression here ----------------------------
20    child = p;
21    while (child !== parent) {
22      let next = this.id[child];
23      this.id[child] = parent;
24      child = next;
25    }
26    // --------------------------------------------------------
27    return parent;
28  }

1// same as root(p: number): number
2  find(p: number): number | null {
3
4    if(p < 0 || p >= this.N) {
5      return null
6    }
7
8    let child = p;
9    let parent = this.id[p];
10
11    // in case we find root element, it's value will point to it's own id. 
12    // child is the element / id / node
13    // parent is the value of that id in array, id of another element. sighs
14    while(child !== parent) {
15      child = parent
16      parent = this.id[child]
17    }
18
19    // apply path compression here ----------------------------
20    child = p;
21    while (child !== parent) {
22      let next = this.id[child];
23      this.id[child] = parent;
24      child = next;
25    }
26    // --------------------------------------------------------
27    return parent;
28  }