题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1272

题目描述

上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从5到达8。
http://acm.hdu.edu.cn/data/images/C20-1007-1.jpg

思路

并查集,主要判断是否只有一棵树,以及无闭合。当只输入0 0的时候输出Yes。

AC代码

/*************************************************************************
    > File Name: 1272.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-07-04 Sat 19:40:28 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
const int _max=100000;
static int room[_max+10];
int find(int root) { // 找到树的根节点,以及路径压缩
    int x = root;
    while(root!=room[root])
        root = room[root];
    while(x!=room[root]) { // 路径压缩
        int t = room[x];
        room[x] = root;
        x = t;
    }
    return root;
}
void merge(int a, int b) { // 合并
    int fx=find(a);
    int fy=find(b);
    if(fx!=fy)
        room[fx] = fy;
}


int main()
{
#ifdef Oj
    freopen("1272.in", "r", stdin);
#endif
    int a, b;

    bool visited[_max+10]; // 标记输入迷宫的房间编号
    while(1) {
        for (int i = 1; i <= _max; ++i)
            room[i] = i; // 初始化
        memset(visited, 0, sizeof(visited));

        bool flag = true; // 这个标记用来判断是否闭合,默认是不闭合。
        while(scanf("%d%d", &a, &b) && a+b) {
            if(a==-1&&b==-1) 
                return 0;
            visited[a] = true;
            visited[b] = true;
            if(find(a) == find(b)) // 有相同的根节点,说明之前有过一条路径,则这个为闭合路径。
                flag = false; // 闭合
            else
                merge(a, b); // 不然的话就合并
        }
        int count = 0; // 用来统计树的棵树
        int use = 0; // 用来统计房间数量,房间数为0输出Yes
        for(int i=1;i<=_max; ++i) {
            if(visited[i] && room[i] == i) // 以根节点个数来统计
                ++count;
            if(visited[i] == true) // 统计房间数量
                ++use;
        }
        if(use == 0 || (flag && count == 1)) // 如果房间数量为0或者只有一颗不闭合的树
            puts("Yes");
        else
            puts("No");
    }

    return 0;
}