Skip to content

Instantly share code, notes, and snippets.

@lundstig
Created March 19, 2019 13:59
Show Gist options
  • Save lundstig/cfaf338cf99fbf80632f484ed9566224 to your computer and use it in GitHub Desktop.
Save lundstig/cfaf338cf99fbf80632f484ed9566224 to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
using namespace std;
#define rep(x, s, e) for (int x = int(s); x < int(e); ++x)
int n;
vector<bool> visited;
vector<pair<int, int>> snow;
void dfs(int cur) {
visited[cur] = true;
rep(i, 0, n) {
bool canReach =
snow[cur].first == snow[i].first || snow[cur].second == snow[i].second;
if (canReach && !visited[i]) {
dfs(i);
}
}
}
int main() {
cin >> n;
rep(i, 0, n) {
int x, y;
cin >> x >> y;
snow.push_back({x, y});
}
int components = 0;
visited.assign(n, false);
rep(i, 0, n) {
if (!visited[i]) {
dfs(i);
components++;
}
}
cout << components - 1 << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment