https://codeforces.com/problemset/problem/217/A
Problem - 217A - Codeforces
codeforces.com
// connected component / dfs
#include <bits/stdc++.h>
using namespace std;
vector<int> E[1000];
int V[1000];
int X[1000], Y[1000];
void dfs(int nd)
{
int i, s;
s = E[nd].size();
for (i = 0; i < s; i++) {
if (V[E[nd][i]] == 0) {
V[E[nd][i]] = 1;
dfs(E[nd][i]);
}
}
}
int main()
{
int i, j, n, ans;
cin >> n;
for (i = 0; i < n; i++) {
cin >> X[i] >> Y[i];
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (X[i] == X[j] || Y[i] == Y[j]) {
E[i].push_back(j);
E[j].push_back(i);
}
}
}
ans = 0;
for (i = 0; i < n; i++) {
if (V[i] == 0) {
ans++;
dfs(i);
}
}
ans--;
cout << ans;
return 0;
}

'Algorithm Study > c++' 카테고리의 다른 글
| [C++] Dijkstra(다익스트라 알고리즘) / codeforces-20-C (1) | 2023.06.10 |
|---|---|
| [C++] codeforces-707-B (1) | 2023.06.10 |
| [C++] DFS(Depth-First Search) vs BFS(Breath-First Search) (1) | 2023.06.10 |
| [C++] queue 사용 & 예제 (0) | 2023.06.09 |
| [C++] stack 사용 & 예제 (0) | 2023.06.09 |