05-树8 File Transfer
并查集
简单并查集:输入N,代表有编号为1、2、3……N电脑。下标从1开始。初始化为-1。合并后根为负数,负数代表根,其绝对值代表个数。
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 <= N <= 10^4), 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 <stdio.h> #define MaxN 10001 /* 集合最大元素个数 */ typedef int ElementType; /* 默认元素可以用非负正数表示 */
typedef int SetName; /* 默认用根节点下标作为集合名称 */
ElementType SetType[MaxN]; /* 假设集合元素下标从1开始 */ void Union( ElementType S[], SetName Root1, SetName Root2 );
SetName Find( ElementType S[], ElementType X ); int main()
{
int N;
int computerA,computerB;
scanf("%d",&N);
for(int i = ; i < N+; i++)
SetType[i] = -;
char operation;
scanf("%c",&operation);
while(operation != 'S') {
if(operation == 'I') { //inputting a connection
scanf("%d %d",&computerA, &computerB);
Union(SetType,Find(SetType,computerA), Find(SetType,computerB));
}else if(operation == 'C') { //check
scanf("%d %d",&computerA, &computerB);
if(Find(SetType,computerA) == Find(SetType,computerB)) { //是否是同一个根
printf("yes\n");
}else {
printf("no\n");
}
}
scanf("%c",&operation);
}
int components = ;
for(int i = ; i < N+; i++) {
if(SetType[i] < )
components++;
}
if(components == )
printf("The network is connected.\n");
else
printf("There are %d components.\n",components);
return ;
}
/* 这里默认Root1和Root2是不同集合的根结点 */
void Union( ElementType S[], SetName Root1, SetName Root2 )
{
/* 保证小集合并入大集合 */
if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */
S[Root2] += S[Root1]; /* 集合1并入集合2 */
S[Root1] = Root2;
}
else { /* 如果集合1比较大 */
S[Root1] += S[Root2]; /* 集合2并入集合1 */
S[Root2] = Root1;
}
} SetName Find( ElementType S[], ElementType X )
{ /* 默认集合元素全部初始化为-1 */
if ( S[X] < ) /* 找到集合的根 */
return X;
else
return S[X] = Find( S, S[X] ); /* 路径压缩 */
}
最新文章
- JS复习--更新结束
- Javascript实现前端简单路由
- Java多线程系列--“基础篇”01之 基本概念
- Agreeing to the Xcode/iOS license requires admin privileges, please re-run as root via sudo
- Accelerating Matlab
- Android -- shape 定义控件的属性
- jsp配置项目时出错Deployment failure on Tomcat 6.x. Could not copy all resources to
- 无线电源传输 Wireless Power Consortium (WPC) Communication
- mysql传统主从、双主复制+keepalived配置步骤
- firefox 最新版地址栏后没有生成二维码的工具
- JSF 2.0 + Ajax hello world example
- How to change data dir of mysql?
- Watch gcc at ubuntu 12,See ELF file header
- [PWA] sw-precache
- Linux鸟哥的私房菜(3)— 总体规划和磁盘分区 读书笔记
- 服务器后台代码生成TreeView的json字符串
- [C++]油田(Oil Deposits)-用DFS求连通块
- 【gulp】gulp + browsersync 构建前端项目自动化工作流
- win10装MySQL5.7
- WebMisCentral-Client 适配MySql数据库