파일 전송 (25 분)

나무 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≤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 #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;
}

좋은 웹페이지 즐겨찾기