1일1알

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..

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;..

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..

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..

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..

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

유니온 파인드 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, m; struct Info { int start; int end; int weight; bool operator(const Info& other) const { return weight > other.weight; } }; vector parent; vector height; vector infos; int GetParent(i..

유니온 파인드 #include #include using namespace std; vector parent; vector height; int GetParent(int n) { if (n == parent[n]) return n; return parent[n] = GetParent(parent[n]); } void Merge(int u, int v) { u = GetParent(u); v = GetParent(v); if (u == v) return; if (height[u] > height[v]) ::swap(u, v); parent[u] = v; if (height[u] == height[v]) height[v]++; } int n, m; int main() { cin >> n >> m; paren..

#include #include #include using namespace std; int n, m, k; vector parent; vector height; struct Info { int index; int cost; bool operator(const Info& other) const { return cost > other.cost; } }; vector infos; int GetParent(int n) { if (n == parent[n]) return n; return parent[n] = GetParent(parent[n]); } void Merge(int u, int v) { u = GetParent(u); v = GetParent(v); if (u == v) return; if (hei..

유니온 파인드 자료구조를 이용해서 최소 스패닝 트리를 구하여 절약할 수 있는 최대 비용을 구했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; struct Info { int house1; int house2; int dist; bool operator(const Info& other) const { return dist > other.dist; } }; vector parent; vector he..