Commit171b28e

authored

Update 5.py

1 parent1f363a5 commit171b28eCopy full SHA for 171b28e

File tree

+46

-0

lines changed

+46

-0

lines changed

Lines changed: 46 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,46 @@`
	`1`	`+importsys`
	`2`	`+sys.setrecursionlimit(int(1e5))# 런타임 오류를 피하기 위한 재귀 깊이 제한 설정`
	`3`	`+`
	`4`	`+n=int(input())`
	`5`	`+`
	`6`	`+parent= [0]* (n+1)# 부모 노드 정보`
	`7`	`+d= [0]* (n+1)# 각 노드까지의 깊이`
	`8`	`+c= [0]* (n+1)# 각 노드의 깊이가 계산되었는지 여부`
	`9`	`+graph= [[]for_inrange(n+1)]# 그래프(graph) 정보`
	`10`	`+`
	`11`	`+for_inrange(n-1):`
	`12`	`+a,b=map(int,input().split())`
	`13`	`+graph[a].append(b)`
	`14`	`+graph[b].append(a)`
	`15`	`+`
	`16`	`+# 루트 노드부터 시작하여 깊이(depth)를 구하는 함수`
	`17`	`+defdfs(x,depth):`
	`18`	`+c[x]=True`
	`19`	`+d[x]=depth`
	`20`	`+foryingraph[x]:`
	`21`	`+ifc[y]:# 이미 깊이를 구했다면 넘기기`
	`22`	`+continue`
	`23`	`+parent[y]=x`
	`24`	`+dfs(y,depth+1)`
	`25`	`+`
	`26`	`+# A와 B의 최소 공통 조상을 찾는 함수`
	`27`	`+deflca(a,b):`
	`28`	`+# 먼저 깊이(depth)가 동일하도록`
	`29`	`+whiled[a]!=d[b]:`
	`30`	`+ifd[a]>d[b]:`
	`31`	`+a=parent[a]`
	`32`	`+else:`
	`33`	`+b=parent[b]`
	`34`	`+# 노드가 같아지도록`
	`35`	`+whilea!=b:`
	`36`	`+a=parent[a]`
	`37`	`+b=parent[b]`
	`38`	`+returna`
	`39`	`+`
	`40`	`+dfs(1,0)# 루트 노드는 1번 노드`
	`41`	`+`
	`42`	`+m=int(input())`
	`43`	`+`
	`44`	`+foriinrange(m):`
	`45`	`+a,b=map(int,input().split())`
	`46`	`+print(lca(a,b))`

Comments

(0)