05-树8 File Transfer (25 分)
We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?
Input Specification:
Each input file contains one test case. For each test case, the first line contains N (2), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:
I c1 c2
where I
stands for inputting a connection between c1
and c2
; or
C c1 c2
where C
stands for checking if it is possible to transfer files between c1
and c2
; or
S
where S
stands for stopping this case.
Output Specification:
For each C
case, print in one line the word "yes" or "no" if it is possible or impossible to transfer files between c1
and c2
, respectively. At the end of each case, print in one line "The network is connected." if there is a path between any pair of computers; or "There are k
components." where k
is the number of connected components in this network.
Sample Input 1:
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S
Sample Output 1:
no
no
yes
There are 2 components.
Sample Input 2:
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
I 1 3
C 1 5
S
Sample Output 2:
no
no
yes
yes
The network is connected.
#include <cstdio>
#include <stdlib.h>
typedef int EleType;
const int maxn = 1e5;
int MaxSize; struct SetType{
EleType Data;
int Parent;
} s[maxn]; void init();
void merge_Search();
void judge(int n, int m);
void connect(int n, int m);
int find_root(int child);
void statistic(int maxsize); int main(){
init();
merge_Search();
statistic(MaxSize);
} void init() {
scanf("%d", &MaxSize);
for (int i=; i<MaxSize; i++) {
s[i].Data = i + ;
s[i].Parent = -;
}
} void merge_Search() {
char c;
int n, m; getchar();
scanf("%c", &c); while(c != 'S') {
scanf(" %d %d", &n, &m);
switch (c) {
case 'C':
judge(n, m);
break;
case 'I':
connect(n, m);
}
getchar();
scanf("%c", &c);
}
} void judge(int n, int m) {
if(find_root(n) == find_root(m)) printf("yes\n");
else printf("no\n");
} int find_root(int data) {
int i = data - ;
if(s[i].Parent < ) {
return i;
}
s[i].Parent = find_root(s[i].Parent + );
return s[i].Parent;
} void connect(int n, int m) {
int root1 = find_root(n);
int root2 = find_root(m);
if (root1 != root2) {
if (s[root1].Parent > s[root2].Parent) {
s[root2].Parent += s[root1].Parent;
s[root1].Parent = root2;
}
else {
s[root1].Parent += s[root2].Parent;
s[root2].Parent = root1;
}
} }
void statistic(int MAX) {
int count = ;
for (int i=; i<MAX; i++) {
if(s[i].Parent < ){
count++;
}
}
if(count == ) printf("The network is connected.\n");
else printf("There are %d components.\n", count); }
最新文章
- spring源码分析之<;context:property-placeholder/>;和<;property-override/>;
- Nim教程【十一】
- 系统级I/O 第八周11.9~11.15
- Law of total probability
- Practical Java
- 洛谷P2737 [USACO4.1]麦香牛块Beef McNuggets
- wpf仿QQ之窗体翻转
- oracle查看最大长度
- bzoj1588 [HNOI2002]营业额统计(Treap)
- 在birt中解决引用了不存在的绑定出现的问题
- 3月19日 html(一) html基础内容
- Zookeeper 在Hadoop中的应用
- 【译】ASP.NET MVC 5 教程 - 4:添加模型
- Linux以下银行乱码
- Hadoop学习笔记—5.自定义类型处理手机上网日志
- Redis——windows环境安装redis和redis sentinel部署
- Nginx (三) 使用Keepalived搭建高可用服务
- IO流之字符流知识总结
- httpd基础配置和虚拟主机的配置方法
- 为什么LINQ to XML的性能要优于XmlDocument?