lgvv98

크루스칼 알고리즘과 위상정렬 백준 알고리즘: 최소 스패닝 트리에서 연습할 수 있습니다. ✅ 서로소 집합 6개의 노드가 주어지는데 각 연결 관계는 6 4 1 4 2 3 2 4 5 6 으로 주어집니다. 여기서 각 노드를 비교하고, 노드 번호의 부모를 업데이트 하면서 결국은 사이클이 형성되는지 찾을 수 있습니다. 하지만 이 경우 시간 복잡도에 큰 손해가 발생하는데, 이를 단축시키고자 경로 압축 기법을 사용하곤 합니다. * 경로 압축 기법이란? - find 함수를 재귀적으로 호출하여 부모 테이블 값을 갱신하는 방법입니다. 오늘 주로 알아 볼 내용은 크루스칼 알고리즘이므로 서로소 집합에 대한 내용은 아래 포스팅을 참고해주세요! https://velog.io/@syc1013/%EC%95%8C%EA%B3%A0%EB%..