C++并查集亲戚(Relations)算法实例

本文实例讲述了C++并查集亲戚(Relations)算法。分享给大家供大家参考。具体分析如下：

题目： 亲戚(Relations)

或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及.在这种情况下，最好的帮手就是计算机。

为了将问题简化，你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和B en是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的关心的亲戚关系的提问，以最快的速度给出答案。

参考输入输出格式 输入由两部分组成。

第一部分以N，M开始。N为问题涉及的人的个数(1 ≤ N ≤ 20000)。这些人的编号为1,2,3,…,N。下面有M行(1 ≤ M ≤ 1000000)，每行有两个数ai, bi，表示已知ai和bi是亲戚.

第二部分以Q开始。以下Q行有Q个询问(1 ≤ Q ≤ 1 000 000)，每行为ci, di，表示询问ci和di是否为亲戚。

对于每个询问ci, di，若ci和di为亲戚，则输出Yes，否则输出No。

样例输入与输出

输入
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9

输出
Yes
No
Yes

如果这道题目不用并查集，而只用链表或数组来存储集合，那么效率很低，肯定超时。

代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
int father[20010]; //father[i]表示i的父亲
int Find(int a) //查找其父亲并压缩路径
{
  if(father[a] != a)
    father[a] = Find(father[a]);
  return father[a];
}
int main()
{
  int N,M;
  int a,b;
  scanf("%d%d",&N,&M);
  //给每个元素建立一个集合
  for(int i = 1 ; i <= N ; ++i)
    father[i] = i;
  //合并
  for(int i = 0 ; i < M ; ++i)
  {
    scanf("%d%d",&a,&b);
    a = Find(a);
    b = Find(b);
    father[a] = b;
  }
  //查询
  scanf("%d",&M);
  while(M--)
  {
    scanf("%d%d",&a,&b);
    a = Find(a);
    b = Find(b);
    if(a == b)
      printf("YES\n");
    else
      printf("NO\n");
  }
  return 0;
}

希望本文所述对大家的C++程序设计有所帮助。

赞 (0)

相关推荐

  • C++归并算法实例

    本文实例讲述了C++归并算法.分享给大家供大家参考.具体如下: /* 归并算法:把两个或两个以上的线性表合并在一起,形成一个新的线性表 函数模版的基本使用 程序意图:将两个相同类型的线性表元素排好序,然后将他们组合成一个排好的线性表 */ #include <iostream> using namespace std; const int n = 5; //5个元素 //输出数据元素 template <class T1> void OutPut(T1 out[(2*n)]) {

  • c++11新增的便利算法实例分析

    C++是一门应用非常广泛的程序设计语言,而c++11则新增加了一些便利的算法,这些新增的算法使我们的代码写起来更简洁方便,本文列举一些常用的新增算法,算是做个总结分析,更多的新增算法读者可以参考:http://en.cppreference.com/w/cpp/algorithm. 算法库新增了三个用于判断的算法all_of.any_of和none_of,定义如下: template< class InputIt, class UnaryPredicate > bool all_of( Inp

  • C++实现简单遗传算法

    本文实例讲述了C++实现简单遗传算法.分享给大家供大家参考.具体实现方法如下: //遗传算法 GA #include<iostream> #include <cstdlib> #include<bitset> using namespace std; const int L=5; //定义编码的长度 int f(int x) //定义测设函数f(x) { int result; result=x*x*x-60*x*x+900*x+100; return result;

  • C++实现自底向上的归并排序算法

    C++实现自底向上的归并排序算法

    本文实例讲述了C++实现自底向上的归并排序算法.分享给大家供大家参考,具体如下: 一. 算法描述 自底向上的归并排序:归并排序主要是完成将若干个有序子序列合并成一个完整的有序子序列:自底向上的排序是归并排序的一种实现方式,将一个无序的N长数组切个成N个有序子序列,然后再两两合并,然后再将合并后的N/2(或者N/2 + 1)个子序列继续进行两两合并,以此类推得到一个完整的有序数组.下图详细的分解了自底向上的合并算法的实现过程: 二. 算法实现 /*=========================

  • C++中十种内部排序算法的比较分析

    C++中十种内部排序算法的比较分析 #include<iostream> #include<ctime> #include<fstream> using namespace std; #define MAXSIZE 1000 //可排序表的最大长度 #define SORTNUM 10 //测试10中排序方法 #define max 100 //基数排序时数据的最大位数不超过百位: typedef struct node { int data3; int next; }

  • C++线性时间的排序算法分析

    C++线性时间的排序算法分析

    前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入排序,希尔排序).交换排序(冒泡排序,快速排序).选择排序(简单选择排序,堆排序).2-路归并排序(可以参考前一篇文章:各种内部排序算法的实现)等,这些排序算法都有一个共同的特点,就是基于比较. 本文将介绍三种非比较的排序算法:计数排序,基数排序,桶排序.它们将突破比较排序的Ω(nlgn)下界,以线性时间运行. 一.比较排序算法的时间下界 所谓的比较排序是指通过比较来决定元素间的相对次序. "定理:对于含n个元素的一个输入序列,

  • C++实现大数乘法算法代码

    C++实现大数乘法算法代码 复制代码 代码如下: //大数乘法算法 #include<iostream> #include<string> #include<cstring> using namespace std; int main() {     string num1,num2;     cin >> num1 >> num2;     //cout << num1.size() << " " &

  • C++求1到n中1出现的次数以及数的二进制表示中1的个数

    在从 1 到 n 的正数中 1 出现的次数 题目: 输入一个整数 n,求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数. 例如输入 12,从 1 到 12 这些整数中包含 1  的数字有 1, 10, 1 1 和 12, 1 一共出现了 5 次 代码实现(GCC编译通过): #include "stdio.h" #include "stdlib.h" int count1(int n); int count2(int n); int main(void

  • C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    C++实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T t

  • C++实现自顶向下的归并排序算法

    C++实现自顶向下的归并排序算法

    本文实例讲述了C++实现自顶向下的归并排序算法.分享给大家供大家参考,具体如下: 一. 算法描述 自顶向下的归并排序:采用分治法进行自顶向下的程序设计方式,分治法的核心思想就是分解.求解.合并. 1. 先将长度为N的无序序列分割平均分割为两段 2. 然后分别对前半段进行归并排序.后半段进行归并排序 3. 最后再将排序好的前半段和后半段归并 过程(2)中进行递归求解,最终下图详细的分解了自顶向下的合并算法的实现过程: 二. 算法实现 /*==============================

  • C++实现N个骰子的点数算法

    本文实例讲述了C++实现N个骰子的点数算法,分享给大家供大家参考之用.具体方法如下: 题目要求:把n个骰子仍在地上,所有点数 实现代码如下: #include <iostream> using namespace std; const int g_maxValue = 6; const int number = 6; int array[(number - 1) * g_maxValue + 1]; void probility(int original, int current, int s

  • C++实现遗传算法

    本文实例讲述了C++实现简单遗传算法.分享给大家供大家参考.具体实现方法如下: // CMVSOGA.h : main header file for the CMVSOGA.cpp //////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////// #if !defined(AFX_CMV

随机推荐