前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU 1272 小希的迷宫(并查集判断有无成环)

HDU 1272 小希的迷宫(并查集判断有无成环)

作者头像
Ch_Zaqdt
发布2019-01-10 11:28:02
6330
发布2019-01-10 11:28:02
举报
文章被收录于专栏:Zaqdt_ACM

这是一道判断有没有成环的并查集的题,就是每两个点要有唯一的路可到达。不太懂并查集的可以看一下这篇博客传送门

       说一下这道题的思路,首先要判断有没有成环的话,要先想清楚什么时候会成环。

比如以这个图为例,我们输入1和2,1和3,2和4,3和4,当输入完2和4的时候现在pre数组里有pre[2]=1,pre[3]=1,pre[4]=1,当再输入3和4的时候,会发现3和4的根节点一样,这就说明了出现了环,而在没有成环的图中,不会出现两个点的根节点相同这种情况。

       这道题在做的时候就要先判断一下有没有刚才所说的那种情况,有的话肯定是有环存在了,还有就是最后要计算一下根节点数,如果不为1的话,就说明这个图是不连通的,所以也不符合题意。

AC代码:

代码语言:javascript
复制
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100005;
int pre[MAXN];
bool vis[MAXN];
int n,m,a,b,flag;

void init(){
  for(int i=0;i<=MAXN;i++){
    pre[i] = i;
    vis[i] = 0;
  }
}

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

void merge(int x,int y){
  int fx = Find(x);
  int fy = Find(y);
  if(fx != fy){
    pre[fy] = fx;
  }
  else flag = 1;            // 当出现有两个点的根节点相同就会有环出现
}

int main()
{
  while(~scanf("%d%d",&n,&m)){
    if(n == -1 && m == -1) break;
    if(n == 0 && m == 0){         // 特判
      printf("Yes\n");
      continue;
    }
    init();
    flag = 0;
    vis[n] = 1;
    vis[m] = 1;
    merge(n,m);
    while(~scanf("%d%d",&a,&b)){
      if(a == 0 && b == 0) break;
      vis[a] = 1;
      vis[b] = 1;
      merge(a,b);
    }
    if(flag){
      printf("No\n");
      continue;
    }
    else{
      int sum = 0;
      for(int i=0;i<=MAXN;i++){
        if(vis[i] && i == pre[i])sum++;
      }
      if(sum == 1)printf("Yes\n");
      else printf("No\n");
    }
  }
  return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年02月22日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档