題目
原題鏈接：A. Ice Skating
題意
有n個(gè)地點(diǎn)碴开，只能向上下左右方向移動(dòng)并到達(dá)別的點(diǎn)，問(wèn)要能到達(dá)所有地點(diǎn)需要添加幾個(gè)點(diǎn)。
參考了其他作者的思路和代碼发钝。到達(dá)一個(gè)點(diǎn)后，把與這個(gè)點(diǎn)橫或縱坐標(biāo)相同的都記錄波闹，之后只記錄為到達(dá)過(guò)的點(diǎn)酝豪。由于第一個(gè)點(diǎn)會(huì)被記錄，所以減一精堕。
代碼
#include<bits/stdc++.h>
using namespace std;
int n,x[1001]= {0},y[1001]= {0};
bool v[1001];
void dfs(int t){
v[t]=true;
for(int i=0;i<n;i++){
if(!v[i] && (x[i]==x[t] || y[i]==y[t])){
dfs(i);
}
}
}
int main() {
cin>>n;
for(int i=0; i<n; i++) {
cin>>x[i]>>y[i];
}
int ans=0;
for(int i=0;i<n;i++){
if(!v[i]){
dfs(i);
ans++;
}
}
cout<<ans-1;
return 0;
}
