SSL 2060_迷宫_并查集

发布于 2018-01-06  961 次阅读


题目描述

小希非常喜欢玩迷宫游戏,现在她自己设计了一个迷宫游戏。在她设计的迷宫中,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从5到达8。


 

思路

一开始在想的时候发现可以用并查集来写,以为如果我们加入一条边的时候,这两个点就已经可以互相到达了,那么肯定是有另外的道路到达的

比赛是没有注意到不可以是输出"0"而输出了"-1"

对于题目中有"有且仅有"这样的话,我们记录一下有多少个不同的点,加入的边数一定要等于点数-1


#include 
#include 
#include 
using namespace std;
#define fill(x, y) memset(x, y, sizeof(x))
#define max(x, y) ((x) > (y) ? (x) : (y))
#define N 100501
int f[N];
bool fl[N];
inline int read()
{
    int x = 0, p = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') p = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
    return x * p;
}
int find(int x)
{
    if (f[x] == x) return x;
    f[x] = find(f[x]);
    return f[x];
}
int main()
{
    int x = read(), y = read();
    int ans = 1, mx = 0;
    for (int i = 1; i < N; i++)
                f[i] = i;
    int tot = 0, tt = 1;
    while (x != -1 || y != -1)
    {
        if (!fl[x]) mx++;
        if (!fl[y]) mx++;
        fl[x] = fl[y] = 1;
        tt++;
        if (ans != 0)
            if (find(x) != find(y))
            {
                f[find(x)] = find(y);
                tot++;
            }
            else ans = 0;
        x = read(); y = read();
        if (x == 0 && y == 0)
        {
            for (int i = 1; i < N; i++)
                f[i] = i;
            fill(fl, 0);
            if (tot != mx - 1) ans = 0;
            printf("%d\n", ans);
            ans = 1;
            tot = 0;
            tt = 1;
            mx = 0;
            x = read(); y = read();
        }
    }
}

 

]]>