HDU 1272 - 小希的迷宫
传送门
思路
用并查集判断是否存在回路,输入可能存在森林,判断根节点的数目是否大于一。
其实还应该判断是否重复输入,不过我用map判断竟然WA了,不知道什么原因。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define MP(a, b) make_pair(a, b)
using namespace std;
const int MAXN = 100000 + 5;
const int INF = 0x3f3f3f3f;
int pa[MAXN], vis[MAXN];
int Find(int x)
{
return pa[x] == x ? x : pa[x] = Find(pa[x]);
}
int main()
{
//freopen("input.txt", "r", stdin);
int a, b, i, j;
while (scanf("%d%d", &a, &b), a + b != -2)
{
if (a + b == 0)
{
printf("Yes\n");
continue;
}
bool flag = false;
for (i = 1; i <= MAXN; i++)
{
pa[i] = i;
vis[i] = 0;
}
vis[a] = vis[b] = 1;
int x = Find(a), y = Find(b);
pa[x] = y;
while (scanf("%d%d", &a, &b), a + b)
{
if (flag)
continue;
x = Find(a), y = Find(b);
if (x == y)
flag = true;
else
{
vis[a] = vis[b] = 1;
pa[x] = y;
}
}
if (flag)
{
printf("No\n");
continue;
}
int cnt = 0;
bool flgin = false;
for (i = 1; i < MAXN; i++)
if (vis[i] && pa[i] == i)
{
cnt++;
if (cnt > 1)
{
flgin = true;
break;
}
}
printf("%s\n", flgin ? "No" : "Yes");
}
return 0;
}