C++ and look up an example of relative of Relations algorithm

This paper illustrates C++ and Relations algorithm. Share with you for your reference. Specific analysis is as follows:

Title: Relations

Maybe you don't know that one of your friends is a relative of yours. He could be the grandson of your great-grandfather's grandfather's son-in-law's cousin's cousin. If a complete family tree is available, it should be possible to determine whether two people are related or not, but if the nearest common ancestor of two people is several generations away from them, which makes the family tree very large, then the test of kinship is beyond the reach of human beings. In this case, the best helper is the computer.

To simplify the problem, you'll get some information about the relationship, as Marry and Tom are relatives, Tom and B en are relatives, and so on. From this information, you can infer that Marry and Ben are related. Please write a program to answer as quickly as possible our questions about concerned relatives.

The input consists of two parts.

The first part starts with N and M. N is the number of people involved in the problem (1 Or less N Or less 20,000). These people are numbered 1,2,3... , N. There are M rows below (1 Or less M Or less 1000000), and each row has two Numbers ai, bi, indicating that ai and bi are known to be relatives.

The second part starts with Q. The following Q line has Q queries (1 Or less Q Or less 1 000 000 000), and each behavior ci, di, indicates whether ci and di are relatives.

For each query ci, di, output Yes if ci and di are relatives, otherwise output No.

Sample input and output

The input
10 7
2, 4
5, 7
1 3
8 and 9
1 2
5 and 6
2, 3,
3
3, 4,
7 to 10
8 and 9

The output
Yes
No
Yes

If this problem does not use a merge lookup, but only a linked list or an array to store the collection, then it is inefficient and will definitely time out.

The code is as follows:

#include <iostream>
#include <cstdio>
using namespace std;
int father[20010]; //Father [I] is my father
int Find(int a) //Find its father and compress the path
{
  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);
  //Create a set for each element
  for(int i = 1 ; i <= N ; ++i)
    father[i] = i;
  //merge
  for(int i = 0 ; i < M ; ++i)
  {
    scanf("%d%d",&a,&b);
    a = Find(a);
    b = Find(b);
    father[a] = b;
  }
  //The query
  scanf("%d",&M);
  while(M--)
  {
    scanf("%d%d",&a,&b);
    a = Find(a);
    b = Find(b);
    if(a == b)
      printf("YESn");
    else
      printf("NOn");
  }
  return 0;
}

Hope that the article described in the C++ programming to help you.