# 1101. The Earliest Moment When Everyone Become Friends
### :memo: Question
----

### :memo: 題意
----
* 給予一串 array [[1,0,1], [2,1,2]], n = 3
* array => [[time, people1, people2]], n 是有幾個人
* time 是 p1 和 p2 認識的時間點，當 p1 認識 p2 後，p2 認識 p3 等於 p1 也認識 p3 了
* 問請問哪個時間點全部人都互相認識了？

### :memo: 我的思考
----
* :medal: **思考一**: 關係圖所以跟 graph 有關，for loop 整個資料當有新關係被加入後，用一個 dfs 去跑這個關係圖，如果裡面所有人都被拜訪到且裡面的人數等於題目給的人數代表這是我們要的答案。
* graph
* dfs

### :memo: mycode
----

class Solution:
    def earliestAcq(self, logs: List[List[int]], n: int) -> int:
        # graph
        # visited = [0 _ for i in ragne(n)]
        # existed = [0 _ for i in range(n)]
        # dfs traverse() 
        
        existed = [0 for i in range(n)]
        graph = [[] for _ in range(n)]
        visited = [0 for _ in range(n)]
        sort_logs = sorted(logs, key = lambda x: x[0])
        
        for time, p1, p2 in sort_logs:
            
            graph[p1].append(p2)
            graph[p2].append(p1)
            existed[p1] = 1
            existed[p2] = 1
            visited[p1] = time
            self.dfs(visited, graph, p1, time)
            if sum(existed) == n and sum(visited) == time * n:
                return time
        
        return -1

    def dfs(self, visited, graph, p, time):
        for next_friend in graph[p]:
            # if not visited[next_friend]:
            if visited[next_friend] != time:
                visited[next_friend] = time
                # visited[next_friend] = 1
                self.dfs(visited, graph, next_friend, time)

### :memo: BigO
----
* 時間複雜度: O((n+e)* n)。
* 空間複雜度: O(n)。

### :memo: 解題
----
* **Submit 1 次 成功**
> 但速度慢
* 最後看解答
* unionFind

### :memo: 本題反饋
----
* 需要反覆練習 :ballot_box_with_check:
* 成功寫出 :ballot_box_with_check:
* 請熟悉 unionfind :ballot_box_with_check:
> unionFind 有兩種 quick find & quick union

----
### :memo: 正確解答思考
----
* :medal: **思考一**: 使用 unionfind 去找(兩種 unionfind function)
1. find quick
2. union quick

### :memo: mycode
----

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]
    
    def find(self, a):
        
        while a != self.root[a]:
            a = self.root[a]
        return a
    
    def union(self, a, b):
        rootA = self.find(a)
        rootB = self.find(b)
        
        if rootA != rootB:
            self.root[rootB] = rootA
            return False
        
        return True
    

class Solution:
    def earliestAcq(self, logs: List[List[int]], n: int) -> int:
        # graph
        # visited = [0 _ for i in ragne(n)]
        # existed = [0 _ for i in range(n)]
        # dfs traverse() 
        uf = UnionFind(n)
        
        sort_logs = sorted(logs, key = lambda x : x[0])
        for time, a, b in sort_logs:
            if not uf.union(a, b):
                n -= 1
            
            if n == 1:
                return time
        
        return -1
            

### :memo: BigO
----
* 時間複雜度: O(n * n)。
> 最差情況是 n * log n + n * n
* 空間複雜度: O(n)。