유니온파인드

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 분석 https://www.acmicpc.net/board/view/112226 2가 1에 의해 진실을 알게 되었기 때문에.가 아니라 1번 파티에 지민이가 참석하였을 때, 1번 사람이 있기 때문에 지민이는 진실을 이야기 할 수 밖에 없고, 1번 파티에 참석한 2번 사람은 해당 사실에 대해 알게 되었기 때문에, 다음 파티인 2번에 지민이가 참석 하였기 때문에, 1번 파티에서 진실을 들은 2번이 있기 때문에 지민이는 또 진실을 이야기할 수 밖에 없고, 마지막 파티에 가서도 2..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 분석 [1717번] 집합의 표현 (유니온 파인드) 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현 karla.tistory.com 풀이 """ 유니온파인드 도시 N개 경로 M개 N개의 정수 도시의 연결 정보 마지막 줄 여행 계획 A-B, B-C, A-D, B-D, E-A 여행..

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 신장 트리 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음 N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 더보기 크루스칼 알고리즘 간선 위주의 알고리즘 시작점을 따로 정하지 않고 최소 비용의 간선..

1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 유니온 파인드 여러 노드가 있을 때, 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find연산으로 구성되어 있는 알고리즘 union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산 find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산 원리 1차원 리스트 이용, 각 노드가 모두 대표 노드이므로 리스트는 자신의 인덱스 값으로 초기..