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>
const int maxn = ; void Initialization( int n);
void Input_connection();
int FindFather(int x);
void Check_connection();
void Check_network(int n);
int arr[maxn]; int main()
{
int n;
char in; scanf("%d",&n); Initialization(n); do
{
getchar();
scanf("%c",&in);
switch(in)
{ case 'I':
{
Input_connection();
break;
}
case 'C':
{
Check_connection();
break;
}
case 'S':
{
Check_network(n);
break;
}
}
}while (in != 'S');
return ; } void Initialization( int n)
{
for (int i = ; i <= n; i++)
{
arr[i] = i;
}
} void Input_connection()
{
int u,v;
scanf("%d %d",&u,&v);
int faA = FindFather(u);
int faB = FindFather(v);
if (faA != faB)
{
arr[faA] = faB;
}
} int FindFather(int x)
{
if (arr[x] == x)
{
return x;
}
else
{
return arr[x] = FindFather(arr[x]);
}
} void Check_connection()
{
int u,v;
scanf("%d %d",&u,&v);
int faA = FindFather(u);
int faB = FindFather(v);
if (faA != faB)
{
printf("no\n");
}
else
{
printf("yes\n");
}
} void Check_network(int n)
{
int cnt = ;
for (int i = ; i <= n; i++)
{
if (arr[i] == i)
{
cnt++;
}
} if ( == cnt)
{
printf("The network is connected.");
}
else
{
printf("There are %d components.",cnt);
}
}
最新文章
- iOS学习系列-Apache服务器的配置
- NHibernate实战详解(二)映射配置与应用
- css实现图片闪光效果
- iOS开发UI篇—手写控件,frame,center和bounds属性
- Babelfish(poj 2503)
- 九度OJ 1442 A sequence of numbers
- 使用CLRMD编写一个自己的C#调试器
- 使用搬瓦工搭建javaweb环境
- 0428css样式
- tag cloud的相关资料
- Windows 7 Boot Updater 如何使用
- spring boot中注入jpa时报could not autowire.No beans of &#39;PersonRepository&#39; type found
- TensorFlow.js之根据数据拟合曲线
- docker运行nginx为什么要使用 daemon off
- 使用 requests 进行身份认证
- vue+Element-ui实现分页效果
- java并发之同步辅助类CyclicBarrier和CountDownLatch
- tomcat8源码之架构解析
- centos6挂载U盘
- TYVJ2032 升降梯上