竞赛课第五周（并查集+Treap树的应用）

目的：

（1）熟悉并掌握并查集的应用

（2）熟悉并掌握BST

（3）熟悉并掌握Treap树的建立与应用

实验内容：

1.并查集 poj 1611 嫌疑人

严重急性呼吸系统综合症 (SARS) 是一种病因不明的非典型肺炎，于 2003 年 3 月中旬被公认为全球威胁。为了尽量减少传染给他人，最好的策略是将嫌疑人与其他人分开。
在不传播疾病大学 (NSYSU) 中，有许多学生团体。同组的学生经常互相交流，一个学生可以加入多个组。为防止SARS的可能传播，南洋大学收集了所有学生团体的成员名单，并在其标准操作程序（SOP）中制定了以下规则。
一旦组中的成员成为嫌疑人，则该组中的所有成员都是嫌疑人。
然而，他们发现，当一名学生被认定为嫌疑人时，要识别所有嫌疑人并不容易。你的工作是编写一个找到所有嫌疑人的程序。

输入

输入文件包含几种情况。每个测试用例以一行中的两个整数 n 和 m 开头，其中 n 是学生数，m 是组数。您可以假设 0 < n <= 30000 和 0 <= m <= 500。每个学生都由一个介于 0 和 n-1 之间的唯一整数编号，最初学生 0 在所有情况下都被识别为嫌疑人。这一行后面是 m 个组的成员列表，每组一行。每行都以一个整数 k 开始，它本身表示组中的成员数。在成员数量之后，有 k 个整数代表该组中的学生。一行中的所有整数至少用一个空格分隔。
n = 0 和 m = 0 的情况表示输入结束，不需要处理。

输出

对于每个案例，在一行中输出嫌疑人的数量。

样本输入

100 4

2 1 2

5 10 13 11 12 14

2 0 1

2 99 2

200 2

1 5

5 1 2 3 4 5

1 0

0 0

样本输出

4

1

1

（oj未过）

#include <bits/stdc++.h>
using namespace std;

int a[30000];

int find(int index)//路径压缩&查找
{
    if(a[index] == index)
        return index;
    return a[index] = find(a[index]);
}

int main()
{
	while(1)
	{
		int suspect = 0;
		int n, m;//n 是学生数，m 是组数
		cin>>n>>m;
		if(n == 0 && m == 0)
			return 0;
			
		for(int i=0;i<n;i++)
		{
			a[i] = i; //初始化
		}
		
		for(int i=0;i<m;i++)//m组
		{
			int k;
			cin>>k;//组中的成员数
			int x1, x2;
			cin>>x1; //先读一个，因为k未必是双数
			for(int j=1;j<k;j++)
			{
				cin>>x2; //再读一个
				int boss1 = find(x1);
				int boss2 = find(x2);
				if(boss1 != boss2)
        			a[boss1] = boss2;
			}
		}
		
		//a[0]是嫌疑人，a[i] == a[0]即可找到人数
		for(int i=0;i<n;i++)
		{
			if(a[i] == a[0])
				suspect++;
		}
		cout << "suspect: " << suspect << endl;
	}
	
	
}
/*
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
*/

【运行结果】

2. Treap树的应用 hdu 4585 Shaolin

少林寺的第一个和尚是方丈，作为功夫大师，他规定每个加入少林的年轻和尚，要选一个老和尚来一场功夫战斗。每个和尚有一个独立的id和独立的战斗等级grade，新和尚可以选择跟他的战斗等级最接近的老和尚战斗。

方丈的id是1，战斗等级是109。他丢失了战斗记录，不过他记得和尚们加入少林的早晚顺序。请帮他恢复战斗记录。

输入：第一行是一个整数n，0 <n <=100,000，和尚的人数，但不包括大师本人。下面有n行，每行有两个整数k，g，表示一个和尚的id和战斗等级，0<= k ,g<=5,000,000。和尚以升序排序，即按加入少林的时间排序。最后一行用0表示结束。

输出：按时间顺序给出战斗，打印出每场战斗中新和尚和老和尚的id。

样例输入：

3

2 1

3 3

4 2

0

样例输出：

2 1

3 2

4 2

#include <bits/stdc++.h>
using namespace std;

map<int, int> mp;
const int BuddhistAbbot = 1e9; //方丈等级

int main()
{
	int n;
	while(1)
	{
		cin>>n;
		if(n == 0)
			return 0;
		mp.clear();
		mp[BuddhistAbbot] = 1; //方丈
		while(n--)
		{
			int id, grade;
			cin>>id>>grade;
			mp[grade] = id;
			int ans;
			map<int, int>::iterator it = mp.find(grade);
			if(it == mp.begin())
				ans = (++it)->second;
			else
			{
				map<int, int>::iterator it2 = it;
				it2--;
				it++;
				//比较grade点上下连着的两个和尚，看看哪个差值更小
				if(abs(grade-(it2->first)) <= abs(grade-(it->first)))
					ans = it2->second;
				else
					ans = it->second;
			}
			cout << "fight: new monk:"<< id << " old monk:" << ans << endl;
		
		}
	}
}

/*
3
2 1
3 3
4 2
0
*/