cgy12306
[백준 BoJ] 9372 - 상근이의 여행 본문
// https://www.acmicpc.net/problem/9372
// 상근이의 여행
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
vector<pair<int, int>> edges;
int parent[1002];
int Find(int x) {
if (parent[x] == x) return x;
return parent[x] = Find(parent[x]);
}
void Union(int a, int b) {
a = Find(a);
b = Find(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
void kruskal() {
int cnt = 0;
for (auto e : edges) {
int a = e.first;
int b = e.second;
if (Find(a) != Find(b)) {
Union(a, b);
cnt++;
}
}
cout << cnt <<"\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int N, M;
memset(parent, 0, sizeof(parent));
edges.clear();
cin >> N >> M;
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
edges.push_back(make_pair(a, b));
}
kruskal();
}
}
'Algorithm > C++' 카테고리의 다른 글
[백준 BoJ] 10282 - 해킹 (0) | 2022.01.24 |
---|---|
[백준 BoJ] 2887 - 행성터널 (0) | 2022.01.20 |
[백준 BoJ] 1774 - 우주신과의 교감 (0) | 2022.01.19 |
[백준 BoJ] 4386 - 별자리 만들기 (0) | 2022.01.19 |
[백준 BoJ] 6497 - 전력난 (0) | 2022.01.19 |
Comments