酷暑一夏1

不忘初心,方得始终


CodeVS1365 欲火银河星际跳跃 题解

题目

小 K 又在玩浴火银河了。。。不过这次他的目的不是跑运输赚钱,而是做任务赚钱。
他想知道关于一个任务的两个星系是否可以连通。

题解

并查集。若两节点联通就把他们放在同一集合中,对于每个询问判断是否在同一集合中即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<cstdio>
const int MAXN=20000+5;
int father[MAXN];
int find(int x){return x==father[x]?x:father[x]=find(father[x]);}
void merge(int x,int y){father[find(x)]=find(y);}
int main()
{
int n,m,q,x,y;
scanf("%d %d %d",&n,&m,&q);
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
merge(x,y);
}
for(int i=1;i<=q;i++)
{
scanf("%d %d",&x,&y);
printf("%s\n",find(x)==find(y)?"Yes":"No");
}
return 0;
}
Error: Not Found
最近的文章

CodeVS1165 字符串的展开 题解

题目在初赛普及组的“阅读程序写结果”的问题中,我们曾给出一个字符串展开的例子:如果在输入的字符串中,含有类似于“d-h”或“4-8”的子串,我们就把它当作一种简写,输出时,用连续递增的字母或数字串替代其中的减号,即,将上面两个子串分别输出为“defgh”和“45678”。在本题中,我们通过增加一些参 …

于  CodeVS, NOIP, 提高组 继续阅读
更早的文章

USACO 2017 February Contest, Silver

ResultThe name and year was hidden.12345* = Correctx = Wrong Answer (including possibly empty or missing output file)Country|Year|Name |Score |helpcross |maxcross |countcrossCHN |····|··········|833 |* x * * x x * x x *|* * * * * * * * * * *|* * * * * * * * * * Solution …

于  USACO, 比赛 继续阅读