解題レポート-PAT-FIle Transfer

解題レポート-PAT-FIle Transfer
原題リンク:https://pta.patest.cn/pta/test/1342/exam/4/question/21732
タイトルの説明:
N個のノードと一連の文字列のシーケンスを入力します.

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S

ここでCは、現在の3 2ノードが連通しているか否かを判断し、連通出力yesであれば出力noを連通しないことを示す.
Iは、ノード2 4を1つのセットにまとめることを示す.
Sは入力終了を示す.
最適化された並列調査セットを使用して問題を解くには、次の手順に従います.

# include 
# include 
# include 
# define MAX 10100
using namespace std;
int S[MAX];

void Initial(int n){
	for(int i=0;i<=n;i++)
		S[i] = -1;
} 

/*
         
int Find(int x){  
    if(S[x] != x)  
        S[x]=Find(S[x]);
    return S[x];  
} 
*/

int Find(int x){
	int k=x,t; //k         。
	//    S        x   
	while(S[x] >= 0) //            
		x=S[x]; 
	//x       
	// k    ，k            ，         
	while(k != x) { 
		t=k; 
		k = S[k]; 
		S[t] = x;
	}
	return x; 
} 

int Union(int x,int y){ //      
	int fx,fy;
    fx = Find(x);
    fy = Find(y);
	if(fx!=fy){
		//        
		if(-(S[fx]) > -(S[fy])){
			S[fx] = S[fx] + S[fy];
			S[fy] = fx;
		}else{
			S[fy] = S[fx] + S[fy];
			S[fx] = fy;
		} 
		return 1;
	}else return 0;//   x,y        	
}
int main(){
	int N,c1,c2;
	char m;
	cin >> N;
	Initial(N); 
	cin >> m;
	while(m!='S'){
		scanf("%d %d",&c1,&c2);
		if(m=='I'){
			Union(c1,c2);
		}else{
    		if(Find(c1) == Find(c2))
    			printf("yes
");
    		else
    			printf("no
");
		}
		cin >> m;
	}
	int co = 0;
	for(int j=1;j<=N;j++){
		if(S[j] < 0)
			co++;
	}
	if(co == 1)
		printf("The network is connected.
");
	else 
		printf("There are %d components.
",co);
	return 0; 
}

いくつかの点に注意してください.
1)検索セットの検索を再帰的な方法に変更することができ,より簡潔であるが,理解しにくい.
2)入力が操作されていない可能性があり,Nを直接入力するとSが入力され,このときN個の構成部分が出力される.
3)この問題は配列を調べてまとめることができ,追加の情報を格納する必要がある場合は,厳格なデータ構造の紹介を参照することができる.

# define SIZE 100
//    :      
struct TreeNode{ //    
	char nameId; //    A,B,C...        ，      
	int parent;  //     ，      
}TreeNode;
TreeNode treeNode[SIZE+1];

//         
int find(TreeNode &treeNode,int x){//  x     
	if(i<1 || i>100)//>100         >n,n     
		return -1;//     
	for(int i=x;treeNode[i].parent>0;i=treeNode[i].parent)
				//  i          0,         ，   
	//    
	for(int k=x;k!=i;k=treeNode[k].parent)// x    ，x                     。
		treeNode[k].parent=i;  //       i，i                

	return i;//       
}

//         
void meget(TreeNode &treeNode,int x,int y){
	//   x,y          
	int fx=find(x);
	int fy=find(y);
	//             ,        ，    。
	if(treeNode[fx].parent>treeNode[fy].parent) //  fx       ，  parent             。
	{
		treeNode[fy].parent += treeNode[fx].parent; //       
		treeNode[fx].parent=fy;
	}else{
		treeNode[fx].parent += treeNode[fx].parent; //       
		treeNode[fy].parent=fx;
	}
}