UVa 793 Network Connections

想法：
　　建disjoint set，把連在一起的電腦放在同一個Set，在判斷兩台電腦是否在同一個Set。具體做法是，

1. 一開始每台電腦都是一個Set(同時該Set的root就是該台電腦編號)
2. 然後要合併兩個Set就先各別找到它們的Root，再從一邊的Root連到另一邊的Root合併成一個Set
3. 要判斷兩台電腦是否在同一個Set也是分別找Root，如果Root一樣表示這兩台電腦在同一個Set。

	#include <cstdio>
	using namespace std;
	int Set[1000001]; // Set[i]= x, x表示i的father, 最上層root的father還是自己
	void MakeSet(int n);
	int FindSetRoot(int x);
	void Union(int x, int y);
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case, C;
	char line[100];
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d ", &C);
	MakeSet(C);
	char Type;
	int A, B;
	int nOfSuccess = 0, nOfUnSuccess = 0;
	while (gets(line)) {
	if (line[0] == '\0') break;
	sscanf(line, "%c %d %d", &Type, &A, &B);
	if (Type == 'c') {
	Union(A,B);
	}
	else {
	if (FindSetRoot(A) == FindSetRoot(B)) //如果同一個root表示在同一個Set
	++nOfSuccess;
	else
	++nOfUnSuccess;
	}
	}
	printf("%d,%d\n", nOfSuccess, nOfUnSuccess);
	if (Case) putchar('\n');
	}
	return 0;
	}
	void MakeSet(int n) // 一開始每個數字都是一個set,自己就是root
	{
	for (int i = 0; i <= n; ++i)
	Set[i] = i;
	}
	int FindSetRoot(int x) // 一直往上找到root
	{
	if (Set[x] == x)
	return x;
	return Set[x] = FindSetRoot(Set[x]); // 前面等號賦値的用意是讓Set深度不要太深
	} // 加速之後尋找速度
	void Union(int x, int y) //將x所屬的Set和y所屬的Set合併成一個Set
	{
	x = FindSetRoot(x);
	y = FindSetRoot(y);
	if (x != y) {
	Set[y] = x;
	}
	}

view raw [UVa] 793 Network Connections.cpp hosted with ❤ by GitHub