﻿HDU 1272 小希的迷宫(并查集||瞎搞)-Ocrosoft

# 小希的迷宫

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 42867    Accepted Submission(s): 13208

Problem Description

Input

Output

Sample Input
```
6 8  5 3  5 2  6 4
5 6  0 0

8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0

3 8  6 8  6 4
5 3  5 6  5 2  0 0

-1 -1

```

Sample Output
```
Yes
Yes
No

```

Author
Gardon

Solution

```#include <set>
#include <map>
#include <cmath>
#include <list>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define msp memset(mp,0,sizeof(mp));
#define msv memset(vis,0,sizeof(vis));
using namespace std;
int n,m;
int pre[100001];
bool vis[100001];
int Find(int x)
{
if(pre[x]==x)return x;
else return Find(pre[x]);
}
void Union(int x,int y)
{
pre[Find(x)]=Find(y);
}
int main()
{
int u,v,sum=0,maxx=0;
bool flag=0;
for(int i=0; i<100001; i++)pre[i]=i;
while(cin>>u>>v)
{
vis[u]=1,vis[v]=1;
maxx=max(max(u,v),maxx);
if(u==-1&&v==-1)break;
if(!u&&!v)
{
if(!flag)
for(int i=1; i<=maxx; i++)
{
if(!vis[i])continue;
if(Find(i)==i)sum++;
if(sum>1)
{
flag=1;
break;
}
}
if(flag)printf("No\n");
else printf("Yes\n");
for(int i=0; i<100; i++)pre[i]=i;
flag=0,sum=0,ms(vis),maxx=0;
}
else
{
int fx=Find(u),fy=Find(v);
//printf("%d %d\n",fx,fy);
if(fx==fy)flag=1;
else Union(fx,fy);
//printf(" %d %d\n",Find(u),Find(v));
}
}
return 0;
}
```

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
set<int> s;
int main()
{
int k,a,b;
while(1)
{
k=1,s.clear();
while(~scanf("%d %d",&a,&b),a+b)
{
if(a+b==-2)return 0;
k++,s.insert(a),s.insert(b);
}
if(k==1||(int)s.size()==k)puts("Yes");
else puts("No");
}
return 0;
}```