任意桶

题目描述：

链接：https://ac.nowcoder.com/acm/problem/15808

平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。
请问至少需要加多少个点，使得点对之间互相可以到达。

输入描述：

第一行一个整数n表示点数（ 1 <= n <= 100)。
第二行n行，每行两个整数xi, yi表示坐标（ 1 <= xi, yi <= 1000)。
y轴正方向为北，x轴正方形为东。

输出描述：

输出一个整数表示最少需要加的点的数目。

solution：

1.首先数据范围是0-100，所以可以通过暴力求解。
2.分析出只有当x或y坐标中的某一个相同时，两点之间才能相互可到达。
3.若是两点之间不可到达，那么只需要增加一个点便可到达。
因此此题可以通过bfs宽搜搜索出有几个连通块，所加点的个数为连通块个数减1

#include <bits/stdc++.h>
using namespace std;
int n,x[105],y[105],vis[105],c=0;
void bfs(int r)
{
    queue<int>q;
    q.push(r);
    vis[r]=1;
    while(!q.empty())
    {
        int rr=q.front();q.pop();
        for(int i=0;i<n;i++)
        {
            if(vis[i])continue;
            if(x[i]==x[rr]||y[i]==y[rr])
            {
                q.push(i);
                vis[i]=1;
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>x[i]>>y[i];
    for(int i=0;i<n;i++)
    {
        if(!vis[i])
        {
            if(i!=0)
                c++;
            bfs(i);
        }
    }
    cout<<c;
}