SSL 2060_迷宫_并查集

lzusa 发布于 2018-01-06 0 次阅读

题目描述

小希非常喜欢玩迷宫游戏，现在她自己设计了一个迷宫游戏。在她设计的迷宫中，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间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();
        }
    }
}

 

]]>