목록유니온 파인드 (19)

1일1알

백준 16168번 퍼레이드 C++

https://www.acmicpc.net/problem/16168 16168번: 퍼레이드 첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, www.acmicpc.net 오일러경로 : 노드가 전부 연결되어있고 차수가 홀수인 노드가 0개 또는 2개이라면 한 경로를 한번만 들려서 모든 경로를 돌 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #inc..
알고리즘 2023. 3. 8. 18:03
백준 16398번 행성 연결 C++

https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 유니온 파인드 자료구조를이용해서 최소 스패닝 트리를 구한다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long;..
알고리즘 2023. 3. 7. 19:19
백준 1774번 우주신과의 교감 C++

https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 유니온 파인드 자료구조를 이용해서 최소 스패닝 트리로 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using in..
알고리즘 2022. 12. 10. 14:15
백준 13905번 세부 C++

https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 최소 스패닝 트리 응용해서 최대 스패닝 트리 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int6..
알고리즘 2022. 10. 31. 15:39
백준 15789번 CTP 왕국은 한솔 왕국을 이길 수 있을까? C++

https://www.acmicpc.net/problem/15789 15789번: CTP 왕국은 한솔 왕국을 이길 수 있을까? 입력의 첫째 줄에 왕국의 수 N(3 ≤ N ≤ 100,000)과 동맹 관계의 수 M(1 ≤ M ≤ 200,000)이 주어진다. 이 후 M개의 줄에 X,Y가 주어진다. 이는 X 왕국과 Y 왕국이 동맹이라는 뜻이다. 입력의 마지막 줄에 CT www.acmicpc.net 유니온 파인드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using..
알고리즘 2022. 10. 29. 12:36
백준 17352번 여러분의 다리가 되어 드리겠습니다! C++

https://www.acmicpc.net/problem/17352 height[v]) ::swap(u, v); parent[u] = v; if (height[u] == height[v]) height[v]++; } int main() { cin >> n; height = vector(n + 1, 1); parent = vector(n + 1); for (int i = 1; i > s >> e; Merge(s, e); } int _parent = GetParent(1); int ans = 0; for (int i = 2; i
알고리즘 2022. 10. 12. 17:02
이전 Prev 1 2 3 4 Next 다음