7 - 8 파일 전송 (25 점)
14870 단어 데이터 구조
#include
using namespace std;
typedef int* SetType;
int Find(SetType S,int X);
void Union(SetType S,int Root1,int Root2);
void Input_connection(SetType S);
void Check_connection(SetType S);
void Check_network(SetType S,int n);
int main(){
SetType S;
int n;char in;
cin>>n;
S = new int [n];
for(int i = 0;i<n;i++){
S[i] = -1;
}
do{
cin>>in;
switch(in){
case 'I':Input_connection(S);break;
case 'C':Check_connection(S);break;
case 'S':Check_network(S,n);break;
}
}while(in!='S');
delete(S);
return 0;
}
int Find(SetType S,int X)
{
if(S[X]<0){
return X;
}else{
return S[X] = Find(S,S[X]);
}
}
void Union(SetType S,int Root1,int Root2){
if(S[Root2]<S[Root1]){
S[Root1] = Root2;
}else{
if(S[Root2]==S[Root1]){
S[Root1]--;
}
S[Root2] = Root1;
}
}
void Input_connection(SetType S)
{
int u,v;
int Root1,Root2;
cin>>u>>v;
Root1 = Find(S,u-1);
Root2 = Find(S,v-1);
if(Root1!=Root2){
Union(S,Root1,Root2);
}
}
void Check_connection(SetType S)
{
int u,v;
cin>>u>>v;
int Root1,Root2;
Root1 = Find(S,u-1);
Root2 = Find(S,v-1);
if(Root1==Root2){
cout<<"yes"<<endl;
}else{
cout<<"no"<<endl;
}
}
void Check_network(SetType S,int n)
{
int i,counter = 0;
for(i=0;i<n;i++){
if(S[i]<0)counter++;
}
if(counter==1){
cout<<"The network is connected."<<endl;
}else{
cout<<"There are "<<counter<<" components.
";
}
}