A-B
, D-E
, B-E
, B-D
, E-F
arr = [0]*200
A-B
, D-E
, B-E
, B-D
, E-F
를 전부 union 하면 아래와 같이 저장된다.def setunion(a, b):
# boss 찾기
fa, fb = findboss(a), findboss(b)
if fa == fb: # 각각의 보스가 같으면 이미 같은 그룹
return
arr[ord(fb)] = fa # 다르면 b 보스에 a 보스 각인
def findboss(member):
if arr[ord(member)] == 0: # 자기 자신이 boss 라면
return member # 자기 자신 반환
# 아니라면 최종 boss 찾기
ret = findboss(arr[ord(member)])
return ret
arr = [0]*200
# 보스 찾기
def findboss(member):
if arr[ord(member)] == 0: # 자기 자신이 boss 라면
return member
ret = findboss(arr[ord(member)])
return ret
# 그룹화
def setunion(a, b):
fa, fb = findboss(a), findboss(b)
if fa == fb: # 각각의 보스가 같으면 이미 같은 그룹
return
arr[ord(fb)] = fa # 다르면 b 보스에 a 보스 각인
setunion('A', 'B')
setunion('D', 'E')
setunion('B', 'E')
setunion('B', 'D')
setunion('E', 'F')
def findboss(member):
if arr[ord(member)] == 0:
return member
ret = findboss(arr[ord(member)])
# 경로 단축
arr[ord(member)] = ret
return ret
## 양방향 그래프에서 cycle 발생 여부 확인
arr = [0]*200
def findboss(member):
if arr[ord(member)] == 0:
return member
ret = findboss(arr[ord(member)])
# 경로 단축
arr[ord(member)] = ret
return ret
def setunion(a, b):
fa, fb = findboss(a), findboss(b)
# boss 같으면 1 리턴
if fa == fb:
return 1
arr[ord(fb)] = fa
# N 개의 간선 정보 입력
N = int(input())
edge = [] # 간선 정보 저장할 리스트
for _ in range(N):
edge.append(input().split())
# cycle 발생 여부 출력
answer = 'cycle 미발생'
for i in range(N):
a, b = edge[i]
# boss 같으면 cycle 발생
if setunion(a, b):
answer = 'cycle 발생'
print(answer)
댓글과 좋아요 그리고 의견 감사합니다. ♥️