---
# System prepended metadata

title: Untitled

---

// Union-find

parent: 0           1->0        2->0        3->0           4
set:    A[1, 2, 3], B[3, 6, 5], C[6, 7, 8], D[8, 9, 10], E[10, 11, 1]
                      0
                                  1
                                              2
        A[1, 2, 10], B[3, 6, 5], C[6, 7, 8], D[8, 9, 10],
                      B1->A1       B1    C1   C3
                                                     D1
         -1, A1, A1  A1, B3, B3  B6, C6, C6  -1, D8,  D8
                              
        union
        A set[1,2,3,6,5]
        a.intersect(b)

[AB, C, D]
 A.contains(B.1) -> Bool
     set[index] = A.union(B)
     set[1].remove

findParent(index) {
    if parent[index] != index {
        findParent(parent[index])
    } else {
        return index
    }
}
selfPaernt = findParent(duplicatedSetNum) 
parent[selfIndex] = selfPaernt

                                 
                                                                     

         1  2  3
        /        \
       1 10  11  3 4 5
      /
     1 8 9
    /
   8 6 7
(A, B)
 C, D
 E



Support
Father Mother
    \  /
   Person
   
getParent(id) -> [id]
getChild(id) -> [id]
   
input group: [Person]
 
        Monther of F of John
        |           |
  F of John        M of Marry
   |                    |
John                    Marry

           
       F/A''                  F/M/C
       |       |
F/A'  M/A'     F/C'    M/'C''
|    |          |     |
A               C

[[John, Marry], [A, B]]
    A3-..., etc
   /  A4
  A - A1 - A2  B2  C1  C2  D2
      \     \  |    | /  \ /
              B     C     D
              
 CN2 -> N(N-1) / 2

 isRealted(p1, p2) -> Bool O(N)
 [P1..Pn]               -> O(N^2)
     (P1, P2)
     (P1, P3..Pn)
     ...
     (P2, P3...Pn)
 O(N^3)
 
 [person: [parent]]
 A: [A1, A3]
 B: [A2, B2]
 C: [C1, C2]
 D: 
 input: [A, B, C, D]
 queue: [A, B, C, D, A1, A3, A2, B2, C1, C2]  contains -> O(n) -> log(n)
         1  2  3
 step:
 1: get(A) -> [A1, A3]
 2: get(B) -> [A2, B2]
 3: get(C) -> [C1, C2]
 4: get(D) -> [C2, D2]

Union Set setp2 -> [A, B]
                   [C, D]

        A        B    C    D
     A1  A2    B1 B2
        A3  A4
            B3 (A4==B3)

A: [A3, A1, A2, B, B2,......]

```kotlin=
data class Person (
    val id: Int,
    val fatherId: Int,
    val montherId: Int,
)

val persons: List<Person>
parnets []
|
A, B
|
children []


1. findPersonGrounps(person) -> [Pair(personId, ids)] {
    persionId -> getParent(id) -> [ids]
    persionId -> getChilren(id) -> [ids]
}
    A, B, C, D
    
    A -> [A1...A100]
    B -> getParents -> [A1, B1] -> recursion
      -> 
    C -> B
2. findPersonGrounpsIntersection(groups)

```

```kotlin=

const val PI = 3.14f
const val size = (Int) -> (Int) {

}
1024 -> 10
logN * logN
[2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]
 |  |  |   |      <-   |  ->
[1,2,2, 2,3,4,5,6,7,8,9]
target: 2 -> [1,3]
logN

```