PTA File Transfer 思路分析及代码解析

龙涵蓄

2023-12-01

一、前导

1. 需要掌握的知识

并查集的基本概念

2. 题目信息

题目来源：PTA / 拼题A
题目地址：https://pintia.cn/problem-sets/16/problems/670

二、解题思路分析

1. 题意理解

已知有N部计算机，默认无网络连接。C n₁ n₂ 表示检查两部计算机之间是否存在网络连接；I n₁ n₂ 表示在两部计算机之间添加网络连接；举例：若n₁ n₂存在连接、n₂ n₄存在连接，则n₁ n₄之间可以传送文件，以此类推

1. 1 输入数据

5   \\'5' 代表网络中共有5台计算机，编号从1到5
C 3 2  \\检查 3#计算机 和 2#计算机 之间是否能够传送文件
I 3 2  \\在3#计算机 和 2#计算机 之间添加一根网线
C 1 5  \\检查 1# 和 5 #是否能够传送文件
I 4 5  \\ 在4#计算机 和 5#计算机 之间添加一根网线
I 2 4  \\ 在2#计算机 和 4#计算机 之间添加一根网线
C 3 5  \\检查 3# 和 5 #是否能够传送文件
S  \\结束，统计网络连接情况

1.2 输出数据

no  \\ 对应C 3 2，默认无网络连接，因此不能传送文件
no \\对应C 1 5，1# 和 5 #无网络连接，因此不能传送文件
yes \\对应C 3 5，因为此时 3# 2# 4# 5# 之间存在网络连接，所以可以传送文件
There are 2 components. \\ 1# 和 3# 2# 4# 5# ，共2个。若只有一个网络，输出 The network is connected.

1.3 补充

n₁ 若和其他计算机无网络连接，依据题意 n₁也是一个单一的网络（孤岛），在最后的统计中需要单独计算

2. 思路分析（重点）

该题属于并查集的应用。并查集是树的一种形态：一父多子多孙。结合File Transfer这道题：（1）C n₁ n₂ 对应并查集中的查（两点间网络是否连通）：，只要n₁ n₂有相同的根节点，n₁ n₂必连通。（2）I n₁ n₂对应并查集中的并，将节点n₁ n₂并到相同的根节点下。代码只要正确实现并查两个操作，就可以突破本题。

三、具体实现

1. 弯路和bug

通过Find()查询根节点时，使用while语句会更清晰容易
合并时，小树向大树合并，否则查找效率会越来越低（树偏向一边了）

2. 代码框架（重点）

2.1 采用的数据结构

本题通过一维数组来存储数据最方便：数组的下标对应计算机的编号，数组的值就是其其父节点所在位置。对于根节点，其数组值为负数，数组值的绝对值就是树的元素值。所有节点初始都是根节点，数组值都是-1

void Init(int a[],int n)
{
	for(int i=0;i<n;i++)
		a[i]=root; //every Node is island , root=-1
}

2.2 程序主体框架

首先完成数据的初始化，然后通过switch语句根据关键字 C, I , S分别进行处理：C 对应并查集中的查询，I 对应并查集中的合并，S对应统计

               程序伪码描述
int main()
{	
	1.初始化数据
	2.Switch语句
	{
		C: find();
		I: merge();
		S: count();
	}
	return 0;
}

2.3 各分支函数

1.void Init(int a[],int n); 初始化函数，数组的下标对应计算机的编号，数组的值就是其其父节点所在位置，默认值均为-1：每个节点都是孤岛

void Init(int a[],int n)
{
	for(int i=0;i<n;i++)
		a[i]=root; //every Node is island , root=-1
}

int Find(int a[],int x); 通过find()找到根节点，存储编号与实际编号差1，因此执行减1操作。初始化时如果从1开始，则没有该问题

int Find(int a[],int x)
{
	x--;
	while(a[x]>=0)
		x=a[x];
	return x;
}

void Check(int a[],int x,int y); 检查x,y 的根节点是否相同，若相同，则存在网络连接，调用find()找到根节点，然后比对

void Check(int a[],int x,int y)
{
	int root1,root2;
	root1=Find(a,x);
	root2=Find(a,y);
	if(root1==root2) cout<<"yes"<<endl;
	else cout<<"no"<<endl;
	return;
}

void Merge(int a[],int x,int y); 对应I指令，本质就是并查集中的合并。在合并时，小树向大树合并、合并后统计树的元素个数并更新。小树向大树合并是为了尽量控制树的深度，也就是保持查找效率

void Merge(int a[],int x,int y) 
{
	int root1,root2;
	root1=Find(a,x);
	root2=Find(a,y);
	if(root1!=root2 && a[root1]<=a[root2] ) 
	{
		a[root2]=root1;
		a[root1]--;
	}
	else if(root1!=root2 && a[root1]>a[root2])
	{
		a[root1]=root2;
		a[root2]--;
	}
	return;
}

void Count(int a[],int n); 统计结果，值为负数的节点都需要录入

void Count(int a[],int n)
{
	int count=0;
	for(int i=0;i<n;i++)
		if(a[i]<0)
			count++;
	if(count==1) cout<<"The network is connected."<<endl;
	else cout<<"There are "<<count<<" components."<<endl;
	return;
}

3. 完整编码

#include <cstdlib>
#include <iostream>
using namespace std;

#define root -1;

void Init(int a[],int n);
void Check(int a[],int x,int y);
int Find(int a[],int x);
void Merge(int a[],int x,int y);
void Count(int a[],int n);

int main()
{
	int n;
	cin>>n;
	int a[n];
	
	Init(a,n);  
	
	char ch; int x,y;
	
	do
	{
		cin>>ch;
		switch(ch)
		{
			case'C':			
				cin>>x>>y;
				Check(a,x,y);
				continue;
			case'I':
				cin>>x>>y;
				Merge(a,x,y); 
				continue;
			case'S':
				Count(a,n);
				continue;
		}
		
	}while(ch!='S');
	
	return 0;
} 

void Count(int a[],int n)
{
	int count=0;
	for(int i=0;i<n;i++)
		if(a[i]<0)
			count++;
	if(count==1) cout<<"The network is connected."<<endl;
	else cout<<"There are "<<count<<" components."<<endl;
	return;
}

void Merge(int a[],int x,int y) 
{
	int root1,root2;
	root1=Find(a,x);
	root2=Find(a,y);
	if(root1!=root2 && a[root1]<=a[root2] ) 
	{
		a[root2]=root1;
		a[root1]--;
	}
	else if(root1!=root2 && a[root1]>a[root2])
	{
		a[root1]=root2;
		a[root2]--;
	}
	return;
}

int Find(int a[],int x)
{
	x--;
	while(a[x]>=0)
	{
		x=a[x];
	}
	return x;
}
void Check(int a[],int x,int y)
{
	int root1,root2;
	root1=Find(a,x);
	root2=Find(a,y);
	if(root1==root2) cout<<"yes"<<endl;
	else cout<<"no"<<endl;
	return;
}
void Init(int a[],int n)
{
	for(int i=0;i<n;i++)
		a[i]=root; //every Node is island 
}

四、参考

浙江大学陈越、何钦铭老师主讲的数据结构

其他

2021.10.11代码：
1.全靠过去续命系列

#include <iostream>
using namespace std;

bool Judge(int x, int y); //查
void Merge(int x, int y); //并

int* a; //使用并查集求解；通过数组进行存储：数组下标代表计算机编号，数组元素组代表根结点编号
int main() 
{
	int N;  char Operation;
	cin >> N;

	a = new int[N + 1];
	for (int i = 1; i <= N; i++)
		a[i] = -1; //-1就代表他是根元素 负几就表示该集合下有几个元素
	
	int x, y;
	while (true)
	{
		cin >> Operation;
		if (Operation == 'C')
		{
			cin >> x >> y;
			if (Judge(x, y))
				cout << "yes" << endl;
			else
				cout << "no" << endl;
		}
		else if (Operation == 'I')
		{
			cin >> x >> y;
			Merge(x, y);
		}
		else if (Operation == 'S')
			break;
	}

	int count=0;
	for (int i = 1; i <= N; i++)
	{
		if (a[i]<0)
			count++;
	}
	if (count == 1) cout << "The network is connected." << endl;
	else cout << "There are " << count << " components." << endl;

	return 0;
}

bool Judge(int x, int y)
{
	int r1 = x, r2 = y;
	while (a[r1] > 0) //找到集合的根
		r1 = a[r1];
	while (a[r2] > 0)
		r2 = a[r2];

	if (r1 == r2) //拥有相同的根结点，则可以进行文件传输
		return true;
	else
		return false;
}
void Merge(int x, int y)
{
	int r1 = x, r2 = y;
	while (a[r1] > 0)
		r1 = a[r1];
	while (a[r2] > 0)
		r2 = a[r2];
	if(r1==r2) return; //x y已经处在相同的并查集下，直接返回

	if (a[r1] <= a[r2])
	{
		a[r1] += a[r2];
		a[r2] = r1;	
	}	
	else
	{
		a[r2] += a[r1];
		a[r1] = r2;	
	}	
	return;
}

2.续命之前
完全忘记了并查集了完全忘记了… 囧rz，使用了图方法进行求解：将计算机抽象为一个个图顶点，两台计算机有网线连接抽象为两个顶点之间有边。进行查询时，使用BFS或DFS，如果在一轮查询中（以其中一个顶点为起点进行查询），两个顶点可以遍历到，则可以进行文件传输。
但是，后三个测试点由于超时无法AC… 错误的方法真是慢性自杀啊
但是还是有所收获的，算是提前复习图了

#include <stack>
#include <iostream>
using namespace std;

void BFS(int Start);
void DFS(int Start);
void DefaultChecked();

int N; bool *checked; 

typedef struct Node* PtrAdjNode;
struct Node
{
	int Value;
	PtrAdjNode Next;
};

struct HeadNode
{
	PtrAdjNode Next;
};
struct HeadNode* M;

void Create(int Num);
void Insert(int Start, int End);
bool Judge(int Start, int End);

int main()
{
	cin >> N;
	M = new struct HeadNode[N+1];
	checked = new bool[N]; DefaultChecked();

	Create(N);

	char Operation = 'S';
	int Start, End;
	while (true)
	{
		cin >> Operation;
		if (Operation == 'C')
		{
			cin >> Start >> End;
			
			//BFS(Start);
			DFS(Start);
			if ( checked[Start]&& checked[End])
				cout << "yes" << endl;
			else
				cout << "no" << endl;
			DefaultChecked();
		}
		else if (Operation == 'I')
		{
			cin >> Start >> End;
			Insert(Start, End); Insert(End, Start);
		}
		else if (Operation == 'S')
			break;
	}

	int Count = 0;
	for (int i = 1; i <= N; i++)
	{
		if (!checked[i])
		{
			Count++;
			//BFS(i);
			DFS(i);
		}		
	}

	if (Count == 1)
		cout << "The network is connected.";
	else
		cout << "There are " << Count << " components.";

	return 0;
}

bool Judge(int Start, int End)
{
	PtrAdjNode Node = M[Start].Next;

	while (Node)
	{
		if (End == Node->Value)
			return true;

		Node = Node->Next;
	}

	return false;
}

void Create(int Num)
{
	for (int i = 1; i <= Num; i++)
		M[i].Next = NULL;
		
	return;
}

void Insert(int Start, int End)
{
	PtrAdjNode Node,Tmp;
	Node = new struct Node;
	Node->Value = End;
	Node->Next = NULL;

	Tmp = M[Start].Next;
	M[Start].Next = Node;
	Node->Next = Tmp;

	return;
}

void DFS(int Start)
{
	checked[Start] = true;

	for (int i = 1; i <= N; i++)
		if (Judge(Start, i) && !checked[i])
			DFS(i);

	return;
}

void BFS(int Start)
{
	stack<int> s;
	int Node = Start,Front;

	checked[Node] = true;

	s.push(Node); 
	Front = s.top();

	while (!s.empty())
	{
		Front = s.top();
		s.pop();

		for (int i = 1; i <= N; i++)
		{
			if (Judge(Front,i) && !checked[i])
			{
				checked[i] = true;
				s.push(i);
			}
		}
	}
	return;
}

void DefaultChecked()
{
	for (int i = 1; i <= N; i++)
		checked[i] = false;
	return;
}