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

题目描述

从前有一个国王，他叫小鑫。有一天，他想建一座城堡，于是，设计师给他设计了好多简易图纸，主要是房间的连通的图纸。小鑫希望任意两个房间有且仅有一条路径可以相通。小鑫现在把设计图给你，让你帮忙判断设计图是否符合他的想法。比如下面的例子，第一个是符合条件的，但是，第二个不符合，因为从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，这个在实现上，因为输入不同的边会有重复的点，所以可以使用一个数组来进行标记，标记下已经输入的点，这样统计这个数组就可以得到点的数目了，但是只有这一个条件是不对的，题目中并没有指明图是否连通，所以符合这个条件的还有这样的非连通图：

所以要继续对条件进行筛查，既然是图的连通影响了条件，所以，我们再加一个图的连通的判断条件，使用并查集的方式很简单就可以判断。所以，我们可以得到最后的判断条件就是图连通 && 边数 = 点数- 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;
    }
}