파일 전송 (25 분)
3064 단어 cpp데이터 구조 mooc진 월
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.
본 문 제 는 경로 압축 등 최적화 도 할 수 있 습 니 다. 본인 은 그렇지 않 습 니 다. 진 을 보십시오. 월 선생님
#include #include
using namespace std;
struct node{
int data;
int parent=-1;
};
int size;
int Find(vector &set,int data){
int q=data-1;
while(set[q].parent>0)
q=set[q].parent;
return q;
}
void connect(vector &set,int i,int j){
int m=Find(set,i);
int n=Find(set,j);
if(set[m].parent set[m].parent+=set[n].parent; set[n].parent=m;
}
else {set[n].parent+=set[m].parent; set[m].parent=n;}
}
void query(vector &set,int i,int j){
int m=Find(set,i); int n=Find(set,j);
if(m==n) cout<
else cout< }
int main(){
int i=1,j,num; cin>>size;
num=size;
vector set(size);
for(int p=0;p set[p].data=p+1;
string str; cin>>str;
while(str!="S"){
if(str=="C"){
cin>>i>>j;
query(set,i,j);
}
else{
cin>>i>>j;
connect(set,i,j);
num--;
}
cin>>str;
}
if(num==1)
cout< else
cout< return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
MinGW-W64용 Windows에서 복잡한(실제로는 아님) Boost 컴파일.C++를 사용하는 경우 매우 유용한 수많은 라이브러리를 생성하는 커뮤니티 기반 프로그램인 Boost를 우연히 발견했을 것입니다. 그 중 일부는 C++17부터 포함된 파일 시스템 라이브러리와 같이 C++에 추가되었습니...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.