[网络协议]7-17 文件传输（路径压缩解法）

我们有一个计算机网络和一个双向连接列表。这些连接中的每一个都允许将文件从一台计算机传输到另一台计算机。是否可以将文件从网络上的任何计算机发送到任何其他计算机？

输入规格：

每个输入文件包含一个测试用例。对于每个测试用例，第一行包含N?(2≤N≤104)，网络中的计算机总数。网络中的每台计算机都由一个介于 1 到N.?然后在以下几行中，输入的格式如下：

I c1 c2  

whereI代表在c1和之间输入连接c2；要么

C c1 c2    

whereC代表检查是否可以在c1和之间传输文件c2；要么

S

whereS代表停止这种情况。

输出规格：

对于每种C情况，如果可能或不可能分别在c1和之间传输文件，请在一行中打印“是”或“否”一词c2。在每个案例的末尾，在一行中打印“网络已连接”。如果任何一对计算机之间存在路径；或“有k组件”。其中k是该网络中连接组件的数量。

样本输入 1：

<span style="color:#212529"><code class="language-in">5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S
</code></span>

示例输出 1：

<span style="color:#212529"><code class="language-out">no
no
yes
There are 2 components.
</code></span>

样本输入 2：

<span style="color:#212529"><code class="language-in">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
</code></span>

示例输出 2：

<span style="color:#212529"><span style="background-color:var(--bg-base)"><code class="language-out">no
no
yes
yes
The network is connected.</code></span></span>

AC代码：（结合注释更好理解）?

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10000+10]={0};
int find(int i){//找到根是序号几 
	if(a[i]<0){
		return i;
	}
	else {
		return find(a[i]);
	}
}
//这个connect运用了路径压缩 
void connect(int r1,int r2){//注意a[r1],a[r2]都是负数，他们是根的根  
	if(a[r2]<=a[r1]){//看看哪个根儿子多 
		a[r2]+=a[r1];//用儿子多的根来记录 
		if(a[r1]!=-1){//如果另一个根有儿子，需要让儿子都改姓 
			for(int i=1;i<n+1;i++){
				if(a[i]==r1){
					a[i]=r2;
				}
			}
		}
		a[r1]=r2;//他自己也要改姓 
	}
	else{//同理 
		a[r1]+=a[r2];
		if(a[r2]!=-1){
			for(int i=1;i<n+1;i++){
				if(a[i]==r2){
					a[i]=r1;
				}
			}
		}
		a[r2]=r1;
	}
}
//此connect未用路径压缩 
//void connect(int Root1,int Root2){
//	if(a[Root2]<a[Root1]){
//		a[Root1] = Root2;
//	}else{
//		if(a[Root2]==a[Root1]){
//			a[Root1]--;
//		}
//		a[Root2] = Root1;
//	}
//}
//		for(int i=1;i<n+1;i++){
//			if(a[i]==)
//		}
//	} 
//}
int main(){
	//int n;
	cin>>n;
	for(int i=0;i<n+1;i++){
		a[i]=-1;
	}
	char ch;
	cin>>ch;
	while(ch!='S'){
		if(ch=='C'){
			int n1,n2;
			cin>>n1;
			cin>>n2;
			int root1=find(n1);
			int root2=find(n2);
			if(root1!=-1){
				if(root1==root2){
					cout<<"yes"<<endl;
				}
				else{
					cout<<"no"<<endl;
				}
			}
			else{
				cout<<"no"<<endl;
			}
		}
		else{
			int n1,n2;
			cin>>n1;
			cin>>n2;
			int r1=find(n1);
			int r2=find(n2);
			if(r1!=r2)
				connect(r1,r2);
		}
		cin>>ch;
	}
	int e=0;
	for(int i=1;i<n+1;i++){
		if(a[i]<0){
			e++;
		}
	} 
	if(e>1)
		cout<<"There are "<<abs(e)<<" components."<<endl;
	else{
		cout<<"The network is connected."<<endl;
	}
}