05-树8 File Transfer

题目

大意

有n台电脑,I表示把两台电脑连接在一起,C是检查两台电脑是否连接在一起.如果1和2连接在一起,2和3连接在一起,那么1和3也连接在一起.
是一个典型的并查集应用.

AC代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
int a[10240];
int b[10240];
//并查集操作
int find(int x) { return x == a[x] ? x : a[x] = find(a[x]); }
int main() {
int n, i, j, k;
cin >> n;
for (i = 1; i <= n; i++) a[i] = i;
char op;
int x, y;
while (cin >> op && op != 'S') {
cin >> x >> y;
if (op == 'I') { //合并
int t = find(x);
a[t] = y;
} else { //查询
if (find(x) == find(y))
cout << "yes\n";
else
cout << "no\n";
}
}
for (i = 1; i <= n; i++) {
int t = find(i);
b[t] = 1;
}
int count = 0;
for (i = 1; i <= n; i++) {
if (b[i] == 1) {
count++;
}
}
if (count == 1) {
cout << "The network is connected.\n";
} else {
cout << "There are " << count << " components.\n";
}
return 0;
}

本文标题:05-树8 File Transfer

文章作者:admin

发布时间:2017年11月21日 - 22:11

最后更新:2017年11月24日 - 18:11

原始链接:https://kxp555.coding.me/2017/11/21/05-树8FileTransfer/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。