题目描述

$N(1\le N\le 1000)$ 头奶牛，编号为 $1\dots N$，在参加一个喝茶时间活动。在喝茶时间活动开始之前，已经有 $M(1\le M\le 2,000)$ 对奶牛彼此认识（是朋友）。第i对彼此认识的奶牛通过两个不相同的整数 $A_i$ 和 $B_i$ 给定（$1\le A_i\le N,1\le B_i\le N$）。输入数据保证一对奶牛不会出现多次。 在喝茶时间活动中，如果奶牛 $i$ 和奶牛 $j$ 有一个相同的朋友奶牛 $k$，那么他们会在某次的喝茶活动中去认识对方（成为朋友），从而扩大他们的社交圈。请判断，在喝茶活动举办很久以后（直到没有新的奶牛彼此认识），$Q(1\le Q\le 100)$ 对奶牛是否已经彼此认识。询问j包含一对不同的奶牛编号 $X_j$ 和 $Y_j$（$1\le X_j\le N,1\le Y_j\le N$）。

例如，假设共有 $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$ 号，如上图 © 所示。

输入格式

第 $1$ 行：三个空格隔开的整数：$N$，$M$ 和 $Q$。

第 $2\dots M+1$ 行：第 $i+1$ 行包含两个空格隔开的整数 $A_i$ 和 $B_i$。

第 $M+2\dots M+Q+1$ 行：第 $j+M+1$ 行包含两个空格隔开的整数 $X_j$ 和 $Y_j$，表示询问 $j$。

输出格式

第 $1\dots Q$ 行：如果第 $j$ 个询问的两头奶牛认识， 第 $j$ 行输出 Y。如果不认识，第 $j$ 行输出 N。

输入输出样例 #1

输入 #1

5 3 3 
2 5 
2 3 
4 5 
2 3 
3 5 
1 5 

输出 #1

Y 
Y 
N 

说明/提示

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

思路

看似很神秘，实则有点诈骗的成分。

其实就是并查集板子。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,q,prt[1001];
int getfather(int u)
{
	if(prt[u]==u)
		return u;
	return prt[u]=getfather(prt[u]);
}
void merge(int x,int y)
{
	int xx=getfather(x),yy=getfather(y);
	if(xx!=yy)
		prt[xx]=yy;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
		prt[i]=i;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		merge(x,y);
	}
	for(int i=1;i<=q;i++)
	{
		int x,y;
		cin>>x>>y;
		int xx=getfather(x),yy=getfather(y);
		if(xx!=yy)
			cout<<"N\n";
		else
			cout<<"Y\n";
	}
	return 0;	
}