程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++並查集親戚(Relations)算法實例

C++並查集親戚(Relations)算法實例

編輯:關於C++

C++並查集親戚(Relations)算法實例。本站提示廣大學習愛好者:(C++並查集親戚(Relations)算法實例)文章只能為提供參考,不一定能成為您想要的結果。以下是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++法式設計有所贊助。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved