usaco10jan tea time

题目链接

题解

并查集模板(?)题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

using namespace std;
int fa[1005], rk[1005], n, m, q;
void (){
for(int i = 1; i <= n; ++i)
fa[i] = i, rk[i] = 1;
}
int Find(int x){
if(x == fa[x]) return x;
return (fa[x] = Find(fa[x]));
}
void joint(int x, int y){
int xa = Find(x), ya = Find(y);
if(xa == ya) return ;
if(rk[xa] > rk[ya])
fa[ya] = xa, rk[xa] += rk[ya];
else
fa[xa] = ya, rk[ya] += rk[xa];
}
int main(){
scanf("%d%d%d", &n, &m, &q);
init();
int u, v;
for(int i = 0; i < m; ++i)
scanf("%d%d", &u, &v), joint(u, v);
for(int i = 0; i < q; ++i)
scanf("%d%d", &u, &v), printf("%sn", Find(u) == Find(v) ? "Y" : "N");
return 0;
}