题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1272

这个题看了别人的思路，虽然AC了但是我自己都不知道为什么。

解题思路：题目意思是找到判断是不是连通无环的图，首先想到的就是并查集。

              1判断成环的时候，只要判断输入边的两个点。有一个共同的父节点，那么这两个点就成环。

              2判断连通的时候，只要判断根节点数为1即可。

             注意：当输入的这组数据只有 0 0 时，依然是满足条件的，即应输出 "Yes"。

对这个并查集，还不是很理解，不过只要理解了代码还是很容易的。

我的AC代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

struct node
{
int x,y;
}s[1000000];

int father[1000000];
int hash[1000000];//用来检测是否成环的

int Find(int x)
{
if(x==father[x]) return x;
father[x]=Find(father[x]);
return father[x];
}

void Union(int x,int y)
{
x=Find(x);
y=Find(y);
hash[x]++;//用来检测是否成环的
if(x!=y)
{
father[x]=y;
}
}

int main(void)
{
int n,i,j,k,l;
while(scanf("%d%d",&s[0].x,&s[0].y)==2)
{
memset(hash,0,sizeof(hash));
if(s[0].x==-1&&s[0].y==-1)
return 0;
else if(s[0].x==0&&s[0].y==0)
printf("Yes\n");
else
{
n=1;
while(scanf("%d%d",&s[n].x,&s[n].y)==2)
{
if(s[n].x==0&&s[n].y==0)
break;
n++;
}
for(i=0;i<n;i++)
{
father[s[i].x]=s[i].x;
father[s[i].y]=s[i].y;
}
for(i=0;i<n;i++)
{
Union(s[i].x,s[i].y);
}
k=0;
for(i=0;i<n;i++)
{
if(s[i].x==father[s[i].x])
k++;
if(s[i].y==father[s[i].y])
k++;
}
l=0;
for(i=0;i<n;i++)
{
if(hash[s[i].x]==2)
l++;
if(hash[s[i].y]==2)
l++;
}
if(k==1&&l==0)
printf("Yes\n");
else
printf("No\n");
}
}
return 0;
}

我的代码可能很乱；在网上找了一篇代码

可能更能理解一些,代码更好一些。

  #include<iostream> 2  using namespace std; 3  #define MAX 100005 4  int father[MAX],flag,sign[MAX]; 5   6  int FindSet(int x) 7  { 8      while(x!=father[x]) 9          x=father[x];10      return x;11  }12  13  void Union(int x,int y)14  {15      x=FindSet(x);16      y=FindSet(y);17      if(x!=y)18          father[x]=y;19      else flag=0; //同父节点，成环20  }21  22  int main()23  {24      int i,a,b;25      while(cin>>a>>b)26      {27          if(a==-1&&b==-1) break;28          if(a==0&&b==0)29          { cout<<"Yes"<<endl; continue; }30          for(i=1;i<MAX;i++) 31          {32              father[i]=i;33              sign[i]=0;34          }35          sign[a]=sign[b]=1;36          flag=1;37          Union(a,b);38          while(cin>>a>>b)39          {40              if(a==0&&b==0) break;41              Union(a,b);42              sign[a]=sign[b]=1;43          }44          int k=0;45          for(i=1;i<MAX;i++)46          {47              if(sign[i]&&father[i]==i) //判断根节点k数目48                  k++; 49              if(k>1) flag=0;50          }51          if(flag) cout<<"Yes"<<endl;52          else cout<<"No"<<endl;53      }54      return 0;55  }

HDU-1272-小希的迷宫（并查集）