그래프/유니온 파인드 (6) 썸네일형 리스트형 마을 보호되어 있는 글입니다. 조별경기 보호되어 있는 글입니다. 비용 https://www.acmicpc.net/problem/2463 2463번: 비용 첫 번째 줄에 정점의 수 N (1< ≤ N ≤ 100,000)과 간선의 수 M (1 ≤ M ≤ 100,000)이 빈칸을 사이에 두고 주어진다. 다음 M개의 각 줄에 간선 하나에 대한 정보를 나타내는 세 개의 양의 정수 x,y,w가 빈칸 www.acmicpc.net 무엇인가 분리하거나 끊는 문제가 나오면 그 문제가 '오프라인'인지 부터 확인하자. 오프라인 = 요구하는 것들이 여러개가 있을 때 처리 순서를 바꿔도 아무 문제가 없는 것 이 문제는 문제를 반대로 풀어 간선을 추가하며 합치는 방법을 푼다. https://t-anb.tistory.com/84 백준 2463 비용 https://www.acmicpc.net/proble.. 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 이 구절이 유니온 파인드를 쓰게 만든다! 파티를 모두 union 해버리자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 .. 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net find 연산의 작동 원리 1. parent 배열에 index 값과 value 값이 동일한지 확인 2. 동일하지 않으면 value 값이 가리키는 index 위치로 이동 3. 재귀로 반복 return parent[a] = find(parent[a]); 3. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 대표 노드값으로 변경 이 문제는 유니온 파인드 문제다. 인접 행렬을 for문.. 유니온 파인드 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작www.acmicpc.net유니온 파인드 3가지외워야 한다!! 이 두 함수를 커스텀하는 것이다.1. int find(int a)2. void unionfunc(int a, int b)3. for (int i = 0; i = n; i++) parent[i] = i; find 연산 재귀 이유?대표 노드(조상)에 도달하면재귀를 빠져나오며 거치는 모든 값들을대표 노드값으로 변경한다. 123456.. 이전 1 다음