markdown题面
  • 板块P1551 亲戚
  • 楼主KevTheDev
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/7/19 20:10
  • 上次更新2023/11/4 14:08:18
查看原帖
markdown题面
324095
KevTheDev楼主2021/7/19 20:10

题目背景

若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。

题目描述

规定:xxyy 是亲戚,yyzz 是亲戚,那么 xxzz 也是亲戚。如果 xxyy 是亲戚,那么xx 的亲戚都是yy 的亲戚,yy 的亲戚也都是 xx 的亲戚。

输入格式

第一行:三个整数 n,m,pn,m,p,(n5000, m5000, p5000n\le5000,~m\le5000,~p \le 5000),分别表示有 nn 个人,mm 个亲戚关系,询问 pp 对亲戚关系。

以下 mm 行:每行两个数 MiM_iMjM_j1Mi, MjN1 \le M_i,~M_j\le N,表示 MiM_iMjM_j 具有亲戚关系。

接下来 pp 行:每行两个数 Pi, PjP_i,~P_j,询问 PiPiPjPj 是否具有亲戚关系。

输出格式

pp 行,每行一个 YesNo。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

## 题目背景
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。

## 题目描述
规定:$x$ 和 $y$ 是亲戚,$y$ 和 $z$ 是亲戚,那么 $x$ 和 $z$ 也是亲戚。如果 $x$,$y$ 是亲戚,那么$x$ 的亲戚都是$y$ 的亲戚,$y$ 的亲戚也都是 $x$ 的亲戚。

## 输入格式
第一行:三个整数 $n,m,p$,($n\le5000,~m\le5000,~p \le 5000$),分别表示有 $n$ 个人,$m$ 个亲戚关系,询问 $p$ 对亲戚关系。

以下 $m$ 行:每行两个数 $M_i$,$M_j$,$1 \le M_i,~M_j\le N$,表示 $M_i$ 和 $M_j$ 具有亲戚关系。

接下来 $p$ 行:每行两个数 $P_i,~P_j$,询问 $Pi$ 和 $Pj$ 是否具有亲戚关系。

## 输出格式
$p$ 行,每行一个 `Yes` 或 `No`。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

@SSerxhs

2021/7/19 20:10
加载中...