首页 › 题库 › C/C++编程考级 › C/C++编程八级 › 简答题
简答题 偏难
#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 &lt;bits/stdc++.h&gt; 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&lt;&lt;"Yes"&lt;&lt;endl;   } else {     a[rr] = ll;     cnt--;     // cout&lt;&lt;"No"&lt;&lt;endl;     printf("No\n");   } } int main() {   int m, n, l, r;   while (scanf("%d %d", &amp;n, &amp;m) != EOF) {     cnt = n;     for (int i = 1; i &lt;= n; i++) {       a[i] = i;     }     for (int i = 1; i &lt;= m; i++) {       scanf("%d %d", &amp;l, &amp;r);       // cin&gt;&gt;l&gt;&gt;r;       find(l, r);     }     printf("%d\n", cnt);     // cout&lt;&lt;cnt&lt;&lt;endl;     for (int i = 1; i &lt;= n; i++)       if (a[i] == i)         printf("%d ", i); // cout&lt;&lt;i&lt;&lt;" ";     // cout&lt;&lt;endl;     printf("\n");   }   return 0; }</pre>
这道题暂未补解析。