家族/親戚(relation)

来源:http://www.cnblogs.com/soul-love/archive/2016/07/10/5657214.html
-Advertisement-
Play Games

題目描述 若某個家族人員過於龐大,要判斷兩個是否是親戚,確實還很不容易,現在給出某個親戚關係圖,求任意給出的兩個人是否具有親戚關係。 規定:x和y是親戚,y和z是親戚,那麼x和z也是親戚。如果x,y是親戚,那麼x的親戚都是y的親戚,y的親戚也都是x的親戚。 輸入輸出格式 輸入描述: 第一行:三個整數 ...


題目描述

若某個家族人員過於龐大,要判斷兩個是否是親戚,確實還很不容易,現在給出某個親戚關係圖,求任意給出的兩個人是否具有親戚關係。

規定:x和y是親戚,y和z是親戚,那麼x和z也是親戚。如果x,y是親戚,那麼x的親戚都是y的親戚,y的親戚也都是x的親戚。

輸入輸出格式

輸入描述:

第一行:三個整數n,m,p,(n<=5000,m<=5000,p<=5000),分別表示有n個人,m個親戚關係,詢問p對親戚關係。

以下m行:每行兩個數Mi,Mj,1<=Mi,Mj<=N,表示Ai和Bi具有親戚關係。

接下來p行:每行兩個數Pi,Pj,詢問Pi和Pj是否具有親戚關係。

輸出描述:

P行,每行一個’Yes’或’No’。表示第i個詢問的答案為“具有”或“不具有”親戚關係。

輸入輸出樣例

輸入樣例:

6 5 3

1 2

1 5

3 4

5 2

1 3

1 4

2 3

5 6

輸出樣例:

Yes

Yes

No

思路

並查集。先將已知的親戚關係合併,再尋找要查詢的親戚的根結點。若根結點相同,輸出Yes,反之,輸出No。

代碼

 

#include<stdio.h>
int fa[100000],b[100000];
int find(int x)
{
    if(fa[x]!=x)
      fa[x]=find(fa[x]);
    return fa[x];
}
void unionn(int x,int y)
{
    x=find(x);y=find(y);
    fa[y]=x;
}
int main()
{
    int i,n,m,q,x,y;
    scanf("%d%d%d",&n,&m,&q);
    for(i=1;i<=n;i++)
      fa[i]=i;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        unionn(x,y);
    }
    for(i=1;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        if(find(x)==find(y))
          b[i]=1;
    }
    for(i=1;i<=q;i++)
    {
        if(b[i]==1)
          printf("Yes\n");
        else
          printf("No\n");
    }
    return 0;
}
View Code
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 安裝openssh-serversudo apt-get install openssh-server 查看server是否啟動: ps -ef |grep ssh 如果看到/usr/sbin/sshd -D,說明服務已經啟動,否則服務尚未啟動,那麼需要啟動server: /etc/init.d/s ...
  • ROP的全稱為Return-oriented programming(返回導向編程),這是一種高級的記憶體攻擊技術可以用來繞過現代操作系統的各種通用防禦(比如記憶體不可執行和代碼簽名等)。雖然現在大家都在用64位的操作系統,但是想要扎實的學好ROP還是得從基礎的x86系統開始,但看官請不要著急。 ...
  • 第一部分:安裝redis 現在我們將redis安裝到此目錄 /usr/local/redis 希望將安裝包下載到此目錄 /usr/local/src 那麼安裝過程指令如下: (註:redis官網地址:http://www.redis.io/ 最新版本:3.0.6) 註意上面的最後一行,我們通過PRE ...
  • 1,伺服器系統的安裝會出現錯誤的地方一般都是在Raid 卡驅動 略過Raid 卡配置, 具體 http://jingyan.baidu.com/article/ca41422fddfd201eae99ed30.html 2.準備好2008R2 系統光碟 以下所舉例的是由"用安裝光碟引導啟動安裝"的方 ...
  • 在ASP.NET 2.0 站點根目錄下,只要存在 App_Offline.htm 文件,那麼所有對.aspx的請求都將轉向App_Offline.htm 。而且瀏覽器的地址欄顯示的是所請求的.aspx的URL。這樣當我們的站點需要維護時,只要把App_Offline.htm 拷貝到站點根目錄下即可。 ...
  • 3. 記憶體數據 前面我們知道了,記憶體是按位元組編址,每個地址的存儲單元可以存放8bit的數據。我們也知道CPU通過記憶體地址獲取一條指令和數據,而他們存在存儲單元中。現在就有一個問題。我們的數據和指令不可能剛好是8bit,如果小於8位,沒什麼問題,頂多是浪費幾位(或許按位元組編址是為了節省記憶體空間考慮)。 ...
  • 隨著Linux程式的增多,軟體的安裝過程中經常出現許多令人頭疼的問題,比如,重覆機械的勞動,今天來分享一些解決方法.. ...
  • 我會用幾篇博客總結一下在Linux中進程之間通信的幾種方法,我會把這個開頭的摘要部分在這個系列的每篇博客中都打出來 進程之間通信的方式 管道 消息隊列 信號 信號量 共用存儲區 套接字(socket) 進程間通信(一)—管道傳送門:http://www.cnblogs.com/lenomirei/p ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...