import syssys.setrecursionlimit(10**6)input= sys.stdin.readlinedeffind(target):if target == parent[target]:return target#경로 압축 최적화 - 부모노드로 모두 집합!! parent[target]=find(parent[target])return parent[target]defunion(a,b): a =find(a) b =find(b)#작은 루트 노드 기준으로 합치라!! 같은 그룹으로 묶기if a==b:returnif a < b: parent[b]=aelse: parent[a]=bN,M=map(int,input().split())parent=[i for i inrange(N+1)]for _ inrange(M): x, a, b =map(int,input().split())if x ==0:union(a,b)else:iffind(a)==find(b):print('YES')else:print("NO")
위 그래프에서 잠깐 예시를 들어보면, 만약 3과 4를 잇는다라고 한다면 이는 3-7-5-4의 사이클을 만드는 것 알 수 있습니다.
따라서 위 문제에서 만약 입력받은 두 수의 집합이 같다면 사이클을 만든다는 것을 알 수 있습니다. 위 로직은 다음에 배울 크루스칼에서 나오게 되니 잘 봐두세요!
#사이클 판단#union findimport sysinput=sys.stdin.readline# find 연산deffind(target):if target == parent[target]:return target# 경로 압축 최적화 parent[target]=find(parent[target])return parent[target]# union 연산defunion(a,b): a =find(a) b =find(b)# 작은 루트 노드를 기준으로 합침if a < b: parent[b]= aelse: parent[a]= bN,M=map(int,input().split())parent = [i for i inrange(N)]for j inrange(M): x,y=map(int,input().split())iffind(x)==find(y):print(j+1); exit()union(x,y)print(0)