P2978 [USACO10JAN]下午茶时间Tea Time

    • 280通过
    • 440提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2010
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    N (1 <= N <= 1000) cows, conveniently numbered 1..N all attend a tea time every day. M (1 <= M <= 2,000) unique pairs of those cows have already met before the first tea time. Pair i of these cows who have met is specified by two differing integers A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N). The input never indicates that cows have met each other more than once.

    At tea time, any cow i and cow j who have met a mutual friend cow k will meet sometime during that tea time and thus expand their circle of known cows.

    Determine whether Q (1 <= Q <= 100) pairs of cows have met after tea times are held for long enough that no new cow meetings are occurring. Query j consists of a pair of different cows X_j and Y_j (1 <= X_j <= N; 1 <= Y_j <= N).

    For example, suppose that out of cows 1 through 5, we know that 2 has met 5, 2 has met 3, and 4 has met 5; see (a) below.

       2---3           2---3            2---3
        \              |\  |            |\ /|
    1    \     -->  1  | \ |    -->  1  | X |
          \            |  \|            |/ \|
       4---5           4---5            4---5
        (a)             (b)              (c)

    In the first tea time, cow 2 meets cow 4, and cow 3 meets cow 5; see (b) above. In the second tea time, cow 3 meets cow 4; see (c) above.

    N(1 <= N <= 1000)头奶牛,编号为1..N,在参加一个喝茶时间活动。在喝茶时间活动开始之前,已经有M(1 <= M <= 2,000)对奶牛彼此认识(是朋友)。第i对彼此认识的奶牛通过两个不相同的整数Ai和Bi给定(1<= Ai <= N; 1 <= Bi <= N)。输入数据保证一对奶牛不会出现多次。 在喝茶时间活动中,如果奶牛i和奶牛j有一个相同的朋友奶牛k,那么他们会在某次的喝茶活动中去认识对方(成为朋友),从而扩大他们的社交圈。 请判断,在喝茶活动举办很久以后(直到没有新的奶牛彼此认识),Q(1 <= Q <= 100)对奶牛是否已经彼此认识。询问j包含一对不同的奶牛编号Xj和Yj(1 <= Xj <= N; 1 <= Yj <= N)。 例如,假设共有1..5头奶牛,我们知道2号认识5号,2号认识3号,而且4号认识5号;如下图(a)。

       2---3           2---3            2---3
        \              |\  |            |\ /|
    1    \     -->  1  | \ |    -->  1  | X |
          \            |  \|            |/ \|
       4---5           4---5            4---5
        (a)             (b)              (c)

    在某次的喝茶活动中,2号认识4号,3号认识5号;如上图(b)所示。接下来的喝茶活动中,3号认识4号,如上图(c)所示。

    输入输出格式

    输入格式:

    * Line 1: Three space-separated integers: N, M, and Q

    * Lines 2..M+1: Line i+1 contains two space-separated integers: A_i and B_i

    * Lines M+2..M+Q+1: Line j+M+1 contains query j as two space-separated integers: X_j and Y_j

    行1:三个空格隔开的整数:N,M,和Q

    行2..M+1:第i+1行包含两个空格隔开的整数Ai和Bi

    行M+2..M+Q+1:第j+M+1行包含两个空格隔开的整数Xj和Yj,表示询问j

    输出格式:

    * Lines 1..Q: Line j should be 'Y' if the cows in the jth query have met and 'N' if they have not met.

    行1..Q:如果第j个询问的两头奶牛认识, 第j行输出“Y”。如果不认识,第j行输出“N”

    输入输出样例

    输入样例#1: 复制
    5 3 3 
    2 5 
    2 3 
    4 5 
    2 3 
    3 5 
    1 5 
    
    输出样例#1: 复制
    Y 
    Y 
    N 
    

    说明

    感谢@蒟蒻orz神犇 提供翻译。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。