真是被这道并查集的水题给坑哭了。。。忘记给uset数组初始化我也是醉了。
题目意思是找到判断是不是连通无环的图，首先想到的就是并查集。
1判断成环的时候，只要判断输入边的两个点。有一个共同的父节点，那么这两个点就成环。
2判断连通的时候，只要判断根节点数为1即可。
#include"iostream"
#include"stdio.h"
#include"algorithm"
#include"string.h"
#include"string"
#include"cmath"
#define mx 100005
using namespace std;
int uset[mx];
bool vis[mx],flag;
void make_set()
{
for(int i=;i<mx;i++)uset[i]=i;
}
int Find(int x) {
while(uset[x]!=x) x=uset[x];
return x;
}
void Union(int x,int y)
{
x=Find(x);
y=Find(y);
if(x==y) flag=true;
else
{
uset[y]=x;
}
}
int main()
{
int a,b;
memset(vis,false,sizeof(vis));
flag=false;
make_set();
while(cin>>a>>b,b!=-&&a!=-)
{
if(a==&&b==)
{
if(!flag)
{
int Count=;
for(int i=;i<mx;i++)
{
if(vis[i]&&uset[i]==i) Count++;
if(Count>){flag=true;break;}
}
}
if(flag) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
make_set();
memset(vis,false,sizeof(vis));
flag=false;
continue;
}
vis[a]=true;vis[b]=true;
Union(a,b);
}
return ;
}