# File Transfer

File Transfer–并查集

正常思路

struct setnode {
	int data;       /*data好像没啥屁用还要来一遍遍历，赶紧滚吧*/
	int parent;
}set[maxsize];

int findp(setnode s[], int x) {   /*找到根结点*/
	int i;
	for (i = 0; i < maxsize&&s[i].data != x; i++); //严重增加时间复杂度
	if (i >= maxsize) return -1;
	for (; s[i].parent>=0; i = s[i].parent);
	return i;
	
	/*if (s[i].parent < 0) return x;
	else return x = findp(s[],s[i].parent);*/
}
int unionset(setnode s[]) {   /*直接合并*/
	int a, b;
	scanf("%d %d", &a, &b);
	int root1 = findp(s, a);
	int root2 = findp(s, b);
	if (root1 != root2) s[root1].parent = root2;
	return true;
}

改进

int supers[maxsize];    //s[i]，把数据对i做一个映射，i是递增数据的编号，s[i]同时代表parent

int findnum(int s[], int x) {
	if (s[x] < 0) return x;
	else return s[x] = findnum(s, s[x]);    //用递归将所有子结点连接到根结点上，压缩路径
}

int superunion(int s[]) {  //比较两个树的树高或者节点数，小树贴在大树上，按秩归并
	int a, b;
	scanf("%d %d", &a, &b);
	int root1 = findnum(s, a);      //结合使用压缩路径，因此树高都是2，s[root]设为节点数比较好
	int root2 = findnum(s, b);
	if (s[root1] > s[root2]) {     
		s[root2] += s[root1];
		s[root1] = root2;
	}
	else {
		s[root1] += s[root2];
		s[root2] = root1;
	}
	return true;
}

int check(int s[]) {    /*是否联通*/
	int a, b;
	scanf("%d %d", &a, &b);
	int root1 = findnum(s, a);
	int root2 = findnum(s, b);
	if (root1 == root2) printf("yes\n");
	else printf("no\n");
	return true;
}


void checkset(int s[],int n) {   /*有几个连通集*/
	int i, count;
	count = 0;
	for (i = 0; i < n; i++) {
		if (s[i] < 0) count++;
	}
	if (count == 1) printf("The network is connected.");
	else printf("There are %d components.", count);
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)   /*初始化*/
		supers[i] = -1;
	
	char choice;
	do{
		scanf("%c", &choice);
	switch (choice)
	{
	case 'I':
		superunion(supers);
		break;
	case 'C':
		check(supers);
		break;
	case 'S':
		checkset(supers,n);
		break;
	default:
		break;
	}
	} while (choice != 'S');
	return 0;
}