SDUT 2798 小鑫的城堡（并查集应用）

淩亂°似流年 2022-05-16 07:22 198阅读 0赞

### 题目描述 ###

从前有一个国王，他叫小鑫。有一天，他想建一座城堡，于是，设计师给他设计了好多简易图纸，主要是房间的连通的图纸。小鑫希望任意两个房间有且仅有一条路径可以相通。小鑫现在把设计图给你，让你帮忙判断设计图是否符合他的想法。比如下面的例子，第一个是符合条件的，但是，第二个不符合，因为从5到4有两条路径（5-3-4和5-6-4）。

Input  
多组输入，每组第一行包含一个整数m（m < 100000），接下来m行，每行两个整数，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。  
Output  
每组数据输出一行，如果该城堡符合小鑫的想法，那么输出”Yes”，否则输出”No”。  
Sample Input  
5  
2 5  
2 3  
1 3  
3 6  
4 6  
6  
1 2  
1 3  
3 4  
3 5  
5 6  
6 4  
Sample Output  
Yes  
No

### 分析&代码 ###

这个题目有几个地方需要注意一下，只要注意到这几个地方就很容易了，图中任意的两点之间只有一条路，所以很自然的，我们想到图应该是构成一棵树，那么，判断条件就是**边的数目 = 点的数目 - 1**，这个在实现上，因为输入不同的边会有重复的点，所以可以使用一个数组来进行标记，标记下已经输入的点，这样统计这个数组就可以得到点的数目了，但是只有这一个条件是不对的，题目中并没有指明图是否连通，所以符合这个条件的还有这样的非连通图：  
![这里写图片描述][70]

所以要继续对条件进行筛查，既然是图的连通影响了条件，所以，我们再加一个图的连通的判断条件，使用并查集的方式很简单就可以判断。所以，我们可以得到最后的判断条件就是**图连通 && 边数 = 点数- 1**  
代码如下：

#include<stdio.h>
    #include<stdlib.h>
    #include<memory.h>
    #include<iostream>
    #define N 100005
    using namespace std;
    
    int tree[N];      // 并查集用来标记每个节点的父节点的数组
    int mark[N];      // 标记节点是否已经重复输入的数组
    int m;
    int cou;         // 计数节点的数量
    int a,b;
    int findroot(int x){      // 寻找根节点并降低树高
        if(tree[x]==-1)
            return x;
        else{
            int temp = findroot(tree[x]);
            tree[x] = temp;
            return temp;
        }
    }
    int main(){
        while(cin>>m){
            memset(tree, -1, sizeof(tree));
            memset(mark, 0, sizeof(mark));
            cou = 0;
            for(int i=0; i<m; i++){
                cin>>a>>b;
                if(!mark[a])      //如果输入的点未输入过 那么计数加一
                    cou++;
                if(!mark[b])
                    cou++;
                mark[a] = mark[b] = 1;
                a = findroot(a);
                b = findroot(b);
                if(a!=b)
                    tree[a] = b;     // 在输入的过程中 对于一条边所关联的两个节点，放到一个集合中
                                     // 相当于标记两个节点的根节点指向同一个节点
            }
            int res = 0;
            for(int i=0; i<N; i++){       // 如果某一个节点对应的数组的值是-1 那么这个点就是根节点（一开始我初始化整个数组为-1）
                if(tree[i]==-1 && mark[i])      //注意也要判断mark[i] 防止题目的节点标号不连续
                    res++;                //记录有多少个根节点（连通子图）
            }
            if(res==1 && m==cou-1)       //根节点只有一个表示图是连通的 边数 = 节点数-1 表示是树
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }

以上~

[70]: /images/20220516/2fce028fc15e4d7880b919be8e220241.png