并查集（入门）

并查集实质是一个树状结构，即给出节点之间的关系并存入数据之中，并能够随时查找两节点之间的关系

有关并查集的概念

父节点：

数据库管理中的数据模型中，早期阶段的层次模型和网状模型中，一个属性如果有上一级，则称这个上一级是它的父结点，如果没有上一级，则这个属性则无父结点。

根节点：即没有父节点的节点。

子节点：有父节点得节点

（如下图）

关键代码

根节点查找

首先对于输入数据进行根节点的查询即查到没有父节点为止

int find_root(int x)
{
	if(x == pa[x])
		return x;
	return x=find_root(pa[x]);
}

这段代码只适用于数据较小的并查集，如果数据过大就要进行树的压缩（不断去找节点的父节点并更新他们的父节点），下面是改良后的查找根节点

int find_root(int x)
{
	int x_root=x;
	while(x_root != pa[x_root])
		x_root=pa[x_root];
	int i=x,j;
	while(pa[i] != x_root)
	{
		j=pa[i];
		pa[i]=x_root;
		i=j;
	}
	return x_root;
}

树的和并

当两棵树的节点间有联系是就要进行树的和并，首先还是调用上一个函数找到相联系根节点如果他们的父节点不相同则就将两节点建立联系

void union_vertices(int x,int y)
{
	int x_root=find_root(x);
	int y_root=find_root(y);
	if(x_root != y_root)
		pa[x_root]=y_root;
}

入门模板题(HDU 1213)

How Many Tables

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 51868 Accepted Submission(s): 25713

Problem DescriptionToday is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.

One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.

For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.

Input

The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.

Output

For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.

Sample Input

Sample Output

2
4

直接套（上述）模板

代码样例

#include 
using namespace std;

int parent[1005];

int find_root(int x)
{
	int x_root=x;
	while(parent[x_root] != -1)
		x_root=parent[x_root];
	return x_root;
}

void union_vertices(int x,int y)
{
	int x_root=find_root(x);
	int y_root=find_root(y);
	if(x_root != y_root)
		parent[x_root]=y_root;
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n,m;
		cin >> n >> m;
		memset(parent,-1,sizeof(parent));
		while(m--)
		{
			int x,y;
			cin >> x >> y;
			union_vertices(x,y);
		}
		int ans=0;
		for(int i=1; i <= n; i++)
			if(parent[i] == -1)
				ans++;
		cout << ans << endl;
	}
	return 0;
}