欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++并查集親戚(Relations)算法實(shí)例

 更新時(shí)間:2015年04月20日 14:43:30   作者:司青  
這篇文章主要介紹了C++并查集親戚(Relations)算法,實(shí)例分析了并查集親戚算法的原理與實(shí)現(xiàn)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下

本文實(shí)例講述了C++并查集親戚(Relations)算法。分享給大家供大家參考。具體分析如下:

題目: 親戚(Relations)

或許你并不知道,你的某個(gè)朋友是你的親戚。他可能是你的曾祖父的外公的女婿的外甥的表姐的孫子。如果能得到完整的家譜,判斷兩個(gè)人是否親戚應(yīng)該是可行的,但如果兩個(gè)人的最近公共祖先與他們相隔好幾代,使得家譜十分龐大,那么檢驗(yàn)親戚關(guān)系實(shí)非人力所能及.在這種情況下,最好的幫手就是計(jì)算機(jī)。

為了將問題簡(jiǎn)化,你將得到一些親戚關(guān)系的信息,如同Marry和Tom是親戚,Tom和B en是親戚,等等。從這些信息中,你可以推出Marry和Ben是親戚。請(qǐng)寫一個(gè)程序,對(duì)于我們的關(guān)心的親戚關(guān)系的提問,以最快的速度給出答案。

參考輸入輸出格式 輸入由兩部分組成。

第一部分以N,M開始。N為問題涉及的人的個(gè)數(shù)(1 ≤ N ≤ 20000)。這些人的編號(hào)為1,2,3,…,N。下面有M行(1 ≤ M ≤ 1000000),每行有兩個(gè)數(shù)ai, bi,表示已知ai和bi是親戚.

第二部分以Q開始。以下Q行有Q個(gè)詢問(1 ≤ Q ≤ 1 000 000),每行為ci, di,表示詢問ci和di是否為親戚。

對(duì)于每個(gè)詢問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

如果這道題目不用并查集,而只用鏈表或數(shù)組來存儲(chǔ)集合,那么效率很低,肯定超時(shí)。

代碼如下:

#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);
  //給每個(gè)元素建立一個(gè)集合
  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;
}

希望本文所述對(duì)大家的C++程序設(shè)計(jì)有所幫助。

相關(guān)文章

最新評(píng)論