LCA2 [백준] 3584번 - 가장 가까운 공통 조상 (파이썬) # 가장 가까운 공통 조상 def find_parent(parent, x): result = [x] while parent[x]: result.append(parent[x]) x = parent[x] return result T = int(input()) for _ in range(T): N = int(input()) parent = [0 for _ in range(N+1)] for _ in range(N-1): a, b = map(int, input().split()) parent[b] = a x, y = map(int, input().split()) # 각 부모 리스트 정의 x_parent = find_parent(parent, x) y_parent = find_parent(parent, y) # 깊.. 2022. 5. 1. [백준] 11437번 - LCA (파이썬) # LCA import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) def make_depth(node, dep): visited[node] = True depth[node] = dep for nnode in arr[node]: if not visited[nnode]: parent[nnode] = node make_depth(nnode, dep+1) def lca(x, y): if depth[x] > depth[y]: y, x = x, y while True: if depth[x] == depth[y]: break y = parent[y] for _ in range(depth[x]): if x == y: return x x = parent[x.. 2022. 2. 7. 이전 1 다음
