Python | Union Find | O(n + m + q), O(n) | Beats 99%
CodeComplexity

Time complexity: O(n+m+q). parent uses list() which takes n time. find uses path compression and has a(n) time, which simplifies to constant. It
# Code
```python3 []
class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        parent = list(range(n)) # each node starts as own parent
        and_ = [-1] * n # a[i] is AND weight to get to i node

        def find(node: int) -> int: # returns root of node's path
            if parent[node] != node:
                parent[node] = find(parent[node]) # if parent of node isn't node, then has other parent
            return parent[node] # need to return parent[node] for path compression

        for a, b, w in edges:
            a, b = find(a), find(b) # find roots for each node
            and_[a] &= w # assume same root, add weight to path
            if a != b:
                and_[a] &= and_[b] # different roots, need to also add weight to b
                parent[b] = a # connect b and a

        # return -1 if nodes aren't connected, if are then return weight of root of s and t to get weight along path
        return [-1 if find(s) != find(t) else and_[find(s)] for s, t in query]
```

# Complexity
- Time complexity: $$O(n + m + q)$$. parent uses list() which takes n time. find uses path compression and has a(n) time, which simplifies to constant. Iterating over m edges takes m time, since each iteration performs constant operations. Iterating over q queries also takes q times, since each iteration performs constant operations. Overall is O(n + m + q).

- Space complexity: $$O(n)$$. parent and and_ both have length of n, all other variables are constant space, so n overall.

# Performance

![Screenshot (22).png](https://assets.leetcode.com/users/images/516e649a-bb97-4229-a58b-cc99341295fd_1742513981.9847503.png)

['Union Find', 'Python3']