简答题
偏难
#7348
冰阔落I 老王喜欢喝冰阔落。 初始时刻,桌面上有n杯阔落,编号为1到n。老王总想把其中一杯阔落倒到另一杯中,这样他一次性就能喝很多很多阔落,假设杯子的容量是足够…
冰阔落I
老王喜欢喝冰阔落。
初始时刻,桌面上有n杯阔落,编号为1到n。老王总想把其中一杯阔落倒到另一杯中,这样他一次性就能喝很多很多阔落,假设杯子的容量是足够大的。
有m 次操作,每次操作包含两个整数x与y。
若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯,请输出"Yes";否则,我们将原始编号为y 所在杯子的所有阔落,倒往原始编号为x 所在的杯子,并输出"No"。
最后,老王想知道哪些杯子有冰阔落。
时间限制:10000
内存限制:65536
输入
有多组测试数据,少于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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。