Union

백준 1717 Union

기본 Union, Find 함수 구현

https://www.acmicpc.net/problem/1717

import sys
sys.setrecursionlimit(10 ** 5)

n, m = map(int, input().split())
parent = [i for i in range(n + 1)]

def find_parents(x, parent):
    if x != parent[x]:
        parent[x] = find_parents(parent[x], parent)
    return parent[x]

def union(parent, a, b):
    a = find_parents(a, parent)
    b = find_parents(b, parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

for i in range(m):
    operation, a, b = map(int, sys.stdin.readline().split())
    if operation:
        if find_parents(a, parent) == find_parents(b, parent):
            print("YES")
        else:
            print("NO")
    else:
        union(parent, a, b)

 

백준 1976 Union

https://www.acmicpc.net/problem/1976

n = int(input())
k = int(input())
graph = [[]]

parent = [p for p in range(n + 1)]


def find_parent(x, parent):
    if x != parent[x]:
        parent[x] = find_parent(parent[x], parent)
    return parent[x]


def union(a, b, parent):
    a = find_parent(a, parent)
    b = find_parent(b, parent)
    if a < b:
        parent[b] = a
    elif b < a:
        parent[a] = b


for i in range(1, n + 1):
    graph.append(list(map(int, input().split())))
    for j in range(len(graph[i])):

        if i != j and graph[i][j]:
            union(i, j+1, parent)

path = list(map(int, input().split()))
result = []
for i in range(len(path)):
    result.append(find_parent(path[i],parent))

if len(set(result)) ==1:
    print("YES")
else :
    print("NO")