CodeForces - 218C : Ice Skating（DFS）

比眉伴天荒 2021-11-26 22:02 190阅读 0赞

**Discription**  
Bajtek is learning to skate on ice. He’s a beginner, so his only mode of transportation is pushing off from a snow drift to the north, east, south or west and sliding until he lands in another snow drift. He has noticed that in this way it’s impossible to get from some snow drifts to some other by any sequence of moves. He now wants to heap up some additional snow drifts, so that he can get from any snow drift to any other one. He asked you to find the minimal number of snow drifts that need to be created.

We assume that Bajtek can only heap up snow drifts at integer coordinates.

**Input**  
The first line of input contains a single integer n (1 ≤ n ≤ 100) — the number of snow drifts. Each of the following n lines contains two integers xi and yi (1 ≤ xi, yi ≤ 1000) — the coordinates of the i-th snow drift.

Note that the north direction coinсides with the direction of Oy axis, so the east direction coinсides with the direction of the Ox axis. All snow drift’s locations are distinct.

**Output**  
Output the minimal number of snow drifts that need to be created in order for Bajtek to be able to reach any snow drift from any other one.

**Examples**  
Input  
2  
2 1  
1 2  
Output  
1

Input  
2  
2 1  
4 1  
Output  
0

**题目大意**  
在一个表格上有许多点，只能横向和纵向连线，问需要添加几个点才能将所有的连接起来。

**思路**  
这道题开始我读错题了，以为是需要一笔连起来，然后就一直过不了。后来才知道  
只要连起来就可以，不用非一笔。  
所以可以用dfs做，通过每个点找到能与它相连的部分组成连通块，数一下连通块的个数减一就是所需要加的点的个数。

**AC代码**

#include<bits/stdc++.h>
    using namespace std;
    
    int x[110],y[110],f[110];
    int n,ans;
    
    void dfs(int i)
    {
        f[i]=1;
        for(int j=1;j<=n;j++)
            if(f[j]!=1&&(x[i]==x[j]||y[i]==y[j]))
            dfs(j);
        return ;
    }
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>x[i]>>y[i];
        for(int i=1;i<=n;i++)
            if(f[i]!=1)
            {
                dfs(i);
                ans++;
            }
        cout<<ans-1<<endl;
        return 0;
    }