并查集入门三连:HDU1213 POJ1611 POJ2236

举报
兔老大 发表于 2021/04/20 01:36:43 2021/04/20
【摘要】 HDU1213 http://acm.hdu.edu.cn/showproblem.php?pid=1213 问题描述 今天是伊格纳修斯的生日。他邀请了很多朋友。现在是晚餐时间。伊格纳修斯想知道他至少需要多少桌子。你必须注意到并非所有的朋友都互相认识,而且所有的朋友都不想和陌生人呆在一起。 这个问题的一个重要规则是,如果我告诉你A知道B,B知道C,那意味着A,B,C彼此...

HDU1213

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

问题描述

今天是伊格纳修斯的生日。他邀请了很多朋友。现在是晚餐时间。伊格纳修斯想知道他至少需要多少桌子。你必须注意到并非所有的朋友都互相认识,而且所有的朋友都不想和陌生人呆在一起。

这个问题的一个重要规则是,如果我告诉你A知道B,B知道C,那意味着A,B,C彼此了解,所以他们可以留在一个表中。

例如:如果我告诉你A知道B,B知道C,D知道E,所以A,B,C可以留在一个表中,D,E必须留在另一个表中。所以Ignatius至少需要2张桌子。

输入

输入以整数T(1 <= T <= 25)开始,表示测试用例的数量。然后是T测试案例。每个测试用例以两个整数N和M开始(1 <= N,M <= 1000)。N表示朋友的数量,朋友从1到N标记。然后M行跟随。每一行由两个整数A和B(A!= B)组成,这意味着朋友A和朋友B彼此了解。两个案例之间会有一个空白行。

 

对于每个测试用例,只输出Ignatius至少需要多少个表。不要打印任何空白。

样本输入

2

5 3

1 2

2 3

4 5

 

5 1

2 5

样本输出

2

4

并查集基础题


      #include<cstdio>
      #include<iostream>
      using namespace std;
      int fa[1005];
      int n,m;
      void init()//初始化
      {
      for(int i=0;i<1005;i++)
       fa[i]=i;
      }
      int find(int x)//寻根
      {
      if(fa[x]!=x)
       fa[x]=find(fa[x]);
      return fa[x];
      }
      void union(int x,int y)//判断、合并
      {
      int a=find(x),b=find(y);
      if(a!=b)
       fa[b]=a;
      }
      int main()
      {
      int t;
      scanf("%d",&t);
      while(t--)
       {
      int a,b,cnt=0;
      scanf("%d%d",&n,&m);
       init();
      for(int i=1;i<=m;i++)//合并
       {
      scanf("%d%d",&a,&b);
      union(a,b);
       }
      for(int i=1;i<=n;i++)//统计
       {
       find(i);
      if(find(i)==i)
       cnt++;
       }
      printf("%d\n",cnt);
       }
      return 0;
      }
  
 

POJ1611

http://poj.org/problem?id=1611

描述

严重急性呼吸系统综合症(SARS)是一种病因不明的非典型肺炎,在2003年3月中旬被认为是一种全球性威胁。为了尽量减少对他人的传播,最好的策略是将嫌疑人与其他嫌疑人分开。 
在Not-Spreading-Your-Sickness University(NSYSU),有许多学生团体。同一组中的学生经常互相交流,学生可以加入几个小组。为了防止可能的SARS传播,NSYSU收集所有学生组的成员列表,并在其标准操作程序(SOP)中制定以下规则。 
一旦组中的成员是嫌疑人,该组中的所有成员都是嫌疑人。 
然而,他们发现,当学生被认定为嫌疑人时,识别所有嫌疑人并不容易。你的工作是编写一个找到所有嫌疑人的程序。

输入

输入文件包含几种情况。每个测试用例以一行中的两个整数n和m开始,其中n是学生数,m是组的数量。您可以假设0 <n <= 30000且0 <= m <= 500.每个学生都使用0到n-1之间的唯一整数进行编号,并且最初学生0在所有情况下都被识别为嫌疑人。该行后面是组的m个成员列表,每组一行。每行以整数k开头,表示组中的成员数。在成员数量之后,有k个整数代表该组中的学生。一行中的所有整数由至少一个空格分隔。 


n = 0且m = 0的情况表示输入结束,无需处理。

 

对于每种情况,输出一行中的嫌疑人数量。

样本输入


      100 4
      2 1 2
      5 10 13 11 12 14
      2 0 1
      2 99 2
      200 2
      1 5
      5 1 2 3 4 5
      1 0
      0 0
  
 

样本输出


      4
      1
      1
  
 

 


      #include<iostream>
      #include<cstdio>
      #include<algorithm>
      #include<cstring>
      #include <string>
      using namespace std;
      int a[30001],pre[30001];
      int find(int x)//寻根
      {
      	 if(pre[x]==x)
              return x;
          else
              return pre[x]=find(pre[x]);
      }
      void union(int x, int y)//合并
      {
     	int fx = find(x), fy = find(y);
     	if (fx != fy)
      		pre[fy] = fx;
      }
      int main()
      {
     	int n,m;
     	while (scanf("%d%d", &n, &m) != EOF && (n || m))
      	{
     		int sum = 0;
     		for (int i = 0; i < n; i++)//初始化
      			pre[i] = i;
     		for (int i = 0; i < m; i++)
      		{
     			int k;
     			scanf("%d", &k);
     			if (k >= 1)
      			{
      scanf("%d", &a[0]);
      for (int j = 1; j < k; j++)
       {
      scanf("%d", &a[j]);//接收
      union(a[0], a[j]);//和0号一组
       }
      			}
      		}
     		for (int i = 0; i < n; i++)//统计
     			if (find(i) ==pre[0])
       sum++;
     		printf("%d\n", sum);
      	}
     	return 0;
      }
  
 

 POJ2236

http://poj.org/problem?id=2236

描述

地震发生在东南亚。ACM(亚洲合作医疗团队)已经与膝上电脑建立了无线网络,但是一次意外的余震袭击,网络中的所有计算机都被打破了。计算机一个接一个地修复,网络逐渐开始工作。由于硬件限制,每台计算机只能直接与距离它不远的计算机进行通信。但是,每台计算机都可以被视为两台计算机之间通信的中介,也就是说,如果计算机A和计算机B可以直接通信,或者计算机C可以与A和A进行通信,则计算机A和计算机B可以进行通信。 B. 

在修复网络的过程中,工作人员可以随时进行两种操作,修复计算机或测试两台计算机是否可以通信。你的工作是回答所有的测试操作。 

输入

第一行包含两个整数N和d(1 <= N <= 1001,0 <= d <= 20000)。这里N是计算机的数量,编号从1到N,D是两台计算机可以直接通信的最大距离。在接下来的N行中,每行包含两个整数xi,yi(0 <= xi,yi <= 10000),这是N台计算机的坐标。从第(N + 1)行到输入结束,有一些操作,这些操作是一个接一个地执行的。每行包含以下两种格式之一的操作: 
1。“O p”(1 <= p <= N),表示修复计算机p。 
2.“S p q”(1 <= p,q <= N),这意味着测试计算机p和q是否可以通信。 

输入不会超过300000行。 

产量

对于每个测试操作,如果两台计算机可以通信则打印“SUCCESS”,否则打印“FAIL”。

样本输入


      4 1
      0 1
      0 2
      0 3
      0 4
      O 1
      O 2
      O 4
      S 1 4
      O 3
      S 1 4
  
 

样本输出


      FAIL
      SUCCESS
  
 

 思路:对每次修好的电脑对其它已经修好的电脑遍历,如果距离小于等于最大通信距离就将他们合并。

注意

  1、坐标之后给出的计算机编号都是n+1的。例如O 3,他实际上修理的是编号为2的计算机,因为计算机是从0开始编号的。

  2、比较距离的时候注意要用浮点数比较,否则会WA。

  3、"FAIL"不要写成"FALL"。

  4、字符串输入的时候注意处理好回车,空格等情况。

  5、注意N的范围(1 <= N <= 1001),最大是1001,不是1000。是个小坑,数组开小了可能会错哦。

 


      #include <iostream>
      #include <stdio.h>
      #include <cmath>
      using namespace std;
      #define MAXN 1010
      int dx[MAXN],dy[MAXN]; //坐标
      int par[MAXN]; //x的父节点
      int repair[MAXN] ={0};
      int n;
      void Init()//初始化
      {
      int i;
      for(i=0;i<=n;i++)
       par[i] = i;
      }
      int Find(int x)//寻根
      {
      if(par[x]!=x)
       par[x] = Find(par[x]);
      return par[x];
      }
      void Union(int x,int y)//合并
      {
       par[Find(x)] = Find(y);
      }
      int Abs(int n)//绝对值
      {
      return n>0?n:-n;
      }
      double Dis(int a,int b)//坐标
      {
      return sqrt( double(dx[a]-dx[b])*(dx[a]-dx[b]) + (dy[a]-dy[b])*(dy[a]-dy[b]) );
      }
      int main()
      {
      int d,i;
      //初始化
      scanf("%d%d",&n,&d);
       Init();
      //输入坐标
      for(i=0;i<n;i++){
      scanf("%d%d",&dx[i],&dy[i]);
       }
      //操作
      char cmd[2];
      int p,q,len=0;
      while(scanf("%s",cmd)!=EOF)
       {
      switch(cmd[0])
       {
      case 'O':
      scanf("%d",&p);
       p--;
       repair[len++] = p;
      for(i=0;i<len-1;i++) //遍历所有修过的计算机,看能否联通
      if( repair[i]!=p && Dis(repair[i],p)<=double(d) )
       Union(repair[i],p);
      break;
      case 'S':
      scanf("%d%d",&p,&q);
       p--,q--;
      if(Find(p)==Find(q)) //判断
      printf("SUCCESS\n");
      else
      printf("FAIL\n");
      default:
      break;
       }
       }
      return 0;
      }
  
 

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/82840116

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。