https://www.acmicpc.net/problem/1717
initial
Just an easy typical union find question where if it is a disjoint set, then the parents are not equal.
solution
rmb to put recur limit
import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline
n, m = map(int, input().split())
parent = [i for i in range(n + 1)] # Initialize parent array
def find_parent(node, parent):
if parent[node] != node:
parent[node] = find_parent(parent[node], parent)
return parent[node]
def union(node1, node2, parent):
par1 = find_parent(node1, parent)
par2 = find_parent(node2, parent)
if par1 < par2:
parent[par2] = par1
else:
parent[par1] = par2
for _ in range(m):
a, node1, node2 = map(int, input().split())
if a == 0:
union(node1, node2, parent)
else:
if find_parent(node1, parent) != find_parent(node2, parent):
print("NO")
else:
print("YES")complexity
oh yes union find with path compression is ackermann function so
The time complexity of the Union-Find operations (with path compression and union by rank) is approximately O(m * α(n)), where m is the number of operations (both union and find), and α(n) is the extremely slow-growing inverse Ackermann function. In practice, α(n) is a very small constant, making the time complexity effectively O(m).
The space complexity is O(n), where n is the number of elements. This is because the parent array has a size proportional to the number of elements in the Union-Find data structure. Additionally, the space complexity is influenced by the recursion stack during the recursive calls in the find_parent function. However, with path compression, the maximum depth of the recursion stack is very shallow, and in practice, it's considered constant. Therefore, the space complexity is O(n).
