05-树8 File Transfer
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≤N≤104), 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.
代码长度限制
16 KB
Go (go)
时间限制
400 ms
内存限制
64 MB
Java (javac)
时间限制
400 ms
内存限制
64 MB
Python (python3)
时间限制
400 ms
内存限制
64 MB
其他编译器
时间限制
150 ms
内存限制
64 MB
C++ (g++)
思路:
本题采用并查集,根结点相同则连通,否则不连通。
AC代码:
#include<bits/stdc++.h>
using namespace std;
#define MAX 10002
int father[MAX]; //存放父节点
bool isRoot[MAX];//判断是否是根结点
//查找x所在集合的根节点
int findFather(int x){
if(x==father[x]) return x;
else return father[x]=findFather(father[x]);//直接将根结点赋值为当前结点的父亲节点
}
//合并集合
void Union(int a,int b){
int faA=findFather(a);
int fbB=findFather(b);
if(faA!=fbB)
father[faA]=fbB;
}
int main(){
int N;
cin>>N;
char ch;
int n1,n2;
cin>>ch;
//初始化
for(int i=1;i<=N;i++){
//设置每个元素父节点为自己
father[i]=i;
isRoot[i]=false;
}
while(ch!='S'){
cin>>n1>>n2;
if(ch=='C'){
if(findFather(n1)==findFather(n2)){
cout<<"yes"<<endl;
}
else{
cout<<"no"<<endl;
}
}
if(ch=='I'){
Union(n1,n2);
}
cin>>ch;
}
for(int i=1;i<=N;i++){
isRoot[findFather(i)]=true;//集合的父节点为根
}
int ans=0;//记录集合的数目
for(int i=1;i<=N;i++){
ans+=isRoot[i];
}
if(ans==1){
cout<<"The network is connected.";
}
else{
cout<<"There are "<<ans<<" components.";
}
return 0;
}
相关文章
- OSG-提示“error reading file e:1.jpg file not handled”
- JAVA File Lock
- line 3: /usr/local/arm/4.3.2/bin/arm-none-linux-gnueabi-gcc: No such file or directory
- file not found. nginx php nginx 如何开启解析 PHP 的功能
- linux命令学习——file
- [FAQ] VisualStudio, Source file requires different compiler version (current compiler is 0.6.1+cxxxxxx)
- javascript file cached in server side
- Ubuntu报“xxx is not in the sudoers file.This incident will be reported” 错误解决方法
- Ubuntu报“xxx is not in the sudoers file.This incident will be reported” 错误解决方法
- 已解决zipfile.BadZipFile: File is not a zip file
- item "tracker_server" in file:/***/WEB-INF/lib/***.jar!/fdfs_client.conf not found
- html中#include file的使用方法
- 如果想要跨平台,在file类下有separtor(),返回锁出平台的文件分隔符
- ELK Logstash 输入file插件
- [MySQL] 解决办法:mysqld: File ‘.binlog.index‘ not found (OS errno 13 - Permission denied)