这道并查集题目我的思路是在输入房间号的时候判断房间是否已经被联通过,联通过则标记使得str为No,考虑了房间数为0和自环,给的案例也都通过了,为什么一直wa呢?拜请各位大佬帮忙看看到底错在哪里,这是我的代码:
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<string.h>
//#include<bits\stdc++.h>
//并查集,构造树,若是成环则不符合打印No,否则打印Yes
using namespace std;
const int maxn=1e5+1;
int root[maxn];
int ans[maxn];//存储输入数据节点
int i=1;
void Init(int n)
{
for(int i=1;i<=n;i++){
root[i]=i;
}
}
int Find(int x)
{
while(root[x]!=x){
root[x]=root[root[x]];
x=root[x];
}
return x;
}
void Union(int x,int y)
{
x=Find(x);
y=Find(y);
if(x!=y){
root[x]=min(x,y);
root[y]=min(x,y);
}
}
int main()
{
memset(root,0,sizeof(ans));
memset(ans,0,sizeof(ans));
int x,y;
int i=1;
while(cin>>x>>y){
getchar();
ans[i]=x;
ans[++i]=y;
if(x==-1&&y==-1){
break;
}
if(!x&&!y){
int n=i-2;
Init(n);
string str="Yes";
for(int j=1;j<=n;j++){
if(Find(j)==Find(j+1)){//如果x和y的根节点本来相同的时候偶又把他们连接起来那么就会成环,
str="No";
}
Union(j,j+1);
}
cout<<str<<endl;
cout<<endl;
memset(ans,0,sizeof(ans));
i=1;
}
}
return 0;
}