유니온 파인드

코드 # 유니온 파인드 이용 def find(a, lst): if a != lst[a]: find(lst[a], lst) return lst[a] def union(a,b,lst): a = find(a,lst) b = find(b,lst) import sys sys.setrecursionlimit(10**5) input = sys.stdin.readline def find(a, lst): if a != lst[a]: lst[a] = find(lst[a],lst) return lst[a] def union(a,b,lst): a = find(a,lst) b = find(b,lst) if a < b: lst[b] = a else: lst[a] = b airport = int(input()) gate = [i ..

코드 import sys sys.setrecursionlimit(10**5) input = sys.stdin.readline def find(a, lst): if a != lst[a]: lst[a] = find(lst[a], lst) return lst[a] def union(a, b, lst): a = find(a,lst) b = find(b,lst) if a < b: lst[b] = a else: lst [a] = b tc = int(input()) for i in range(tc): n = int(input()) k = int(input()) parent = [i for i in range(n+1)] for _ in range(k): a,b = map(int, input().split()) unio..

코드1 (dfs) n,m,k = map(int, input().split()) money = [0,*map(int, input().split())] graph = [[] for _ in range(n+1)] visited = [0]*(n+1) for _ in range(m): x,y = map(int, input().split()) graph[x].append(y) graph[y].append(x) moneylist = [] def dfs(a, graph, visited): stack = [a] visited[a] = 1 cost = money[a] while stack: pn = stack.pop() for i in graph[pn]: if not visited[i]: visited[i] = 1 cos..

코드 # 사이클 판별 # 무방향 그래프인 경우 유니온 파인드로 사이클을 판별할 수 있다 # 참고로 유향 그래프인 경우에는 dfs로 판별할 수 있다 import sys sys.setrecursionlimit(10**5) # 재귀 깊이 제한 input = sys.stdin.readline # 빠른 입력 n,m = map(int, input().split()) parent = [i for i in range(n)] # 집합 def find(x,lst): # 트리의 루트 노드를 찾아주는 find 함수 if x != lst[x]: lst[x] = find(lst[x], lst) return lst[x] def union(x,y,lst): # 트리를 합쳐주는 union 함수 x = find(x,lst) y = fi..

서로소 집합 서로소 집합은 집합 관계를 표현하는 자료구조로, 공통 원소가 없는 두 집합을 말한다. 서로소 집합 알고리즘은 union-find 연산으로 구성된다. 그래서 서로소 알고리즘을 union-find 알고리즘으로 부른다고도 한다. union(합집합 연산), find(찾기) union 연산은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산이다. find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. union(x,y): x가 속한 집합과 y가 속한 집합을 합친다. find(x): x가 속한 집합의 대표 번호(루트 노드)를 반환한다. 1. union 연산을 확인하여 서로 연결된 두 노드 A,B를 확인한다. 1-1. A와 B의 루트 노드 A', B'를 찾는다 1-2. A'를..

코드1 import sys sys.setrecursionlimit(10**5) input = sys.stdin.readline n = int(input()) node = [i for i in range(n+1)] def find(a, parent): if a != parent[a]: # 루트 노드가 아니라면 parent[a] = find(parent[a], parent) # 루트 노드를 찾을 때까지 순회 return parent[a] # 루트 노드 반환 def union(a,b,parent): a = find(a, parent) b = find(b, parent) if a < b: # 루트 노드가 작은 값에 큰 값을 붙인다 parent[b] = a else: parent[a] = b for _ in ra..

코드 import sys sys.setrecursionlimit(10**5) # 재귀 깊이 제한 input = sys.stdin.readline # 빠른 입력 n,m = map(int, input().split()) set = [i for i in range(n+1)] # 부모 노드를 기록할 리스트 def find(a, parent): if a != parent[a]: # 루트 노드가 아니라면 parent[a] = find(parent[a], parent) # 루트 노드에 도달할 때까지 순회 return parent[a] # 루트 노드 반환 def union(a,b,parent): # 트리 합치기 a = find(a, parent) # 루트 노드 찾기 b = find(b, parent) if a < b:..