A32862. 冰阔落 I老王喜欢喝冰阔落。初始时刻，桌面上有n杯阔落，编号为1到n。老王总想把其中一杯阔落倒到另一杯中，这样他一次性就能喝很多很多阔落，假设杯子的容量是足够大的。有m 次操作，每次操作包含两个整数x与y。若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯，请输出"Yes"；否则，我们将原始编号为y 所在杯子的所有阔落，倒往原始编号为x 所在的杯子，并输出"No"。最后，老王想知道哪些杯子有…
填空题
困难
知识点
题目描述
冰阔落 I
老王喜欢喝冰阔落。
初始时刻，桌面上有n杯阔落，编号为1到n。老王总想把其中一杯阔落倒到另一杯中，这样他一次性就能喝很多很多阔落，假设杯子的容量是足够大的。
有m 次操作，每次操作包含两个整数x与y。
若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯，请输出"Yes"；否则，我们将原始编号为y 所在杯子的所有阔落，倒往原始编号为x 所在的杯子，并输出"No"。
最后，老王想知道哪些杯子有冰阔落。
输入
有多组测试数据，少于 5 组。 每组测试数据，第一行两个整数 n, m (n, m<=50000)。接下来 m 行，每行两个整数 x, y (1<=x, y<=n)。
输出
每组测试数据，前 m 行输出 "Yes" 或者 "No"。
第 m+1 行输出一个整数，表示有阔落的杯子数量。
第 m+2 行有若干个整数，从小到大输出这些杯子的编号。
样例输入
3 2
1 2
2 1
4 2
1 2
4 3
样例输出
No
Yes
2
1 3
No
No
2
1 4
参考答案
#include <bits/stdc++.h>
using namespace std;
string str;
int a[50000+5],cnt;
int root(int x)
{
if(a[x]==x) return x;
return root(a[x]);
}
void find(int l,int r)
{
int ll=root(l),rr=root(r);
if(ll==rr)
{
printf("Yes\n");
//cout<<"Yes"<<endl;
}
else
{
a[rr] =ll;
cnt--;
//cout<<"No"<<endl;
printf("No\n");
}
}
int main()
{
int m,n,l,r;
while(scanf("%d %d",&n,&m)!=EOF)
{
cnt=n;
for(int i=1;i<=n;i++)
{
a[i]=i;
}
for(int i=1;i<=m;i++)
{
scanf("%d %d",&l,&r);
//cin>>l>>r;
find(l,r);
}
printf("%d\n",cnt);
//cout<<cnt<<endl;
for(int i=1;i<=n;i++)
if(a[i]==i) printf("%d ",i);//cout<<i<<" ";
//cout<<endl;
printf("\n");
}
return 0;
}
上一题
下一题