《算法：C语言实现》_第一部分_连通性问题解决算法

解决连通问题算法
快速-查找算法的一种简单实现。
快速-查找算法结构
该算法的基础是一个整型数组，当且仅当第p个元素和第q个相等时，p和q是连通的。
初始时，数组中的第i个元素的值为i，0<=i<N。为实现p与q的合并操作，我们遍历数组，把所有名为p的元素值改为q（或者将名为q的元素改为p）。
代码结构
从标准输入读取小于N的非负整数对序列（对p-q表示“把对象p连接到q”），并且输出还未连通的输入对。
数组id，每个元素表示一个对象，有以下性质，当且仅当p和q是连通的，id[p]和id[q]相等。
N为常数，可以输入得到它，为动态为它分配id数组。

#include <stdio.h>
#define N 10000
main()
{
	int i,p,q,t,id[N];
	for(i = 0; i<N; i++)  id[i] = i;
	while (scanf("%d %d\n",&p,&q) == 2)//scanf函数的返回值是参数的个数。
	{
		if(id[p] == id[q]) continue;
		for(t = id[p], i = 0; i < N; i++)
			if(id[i] == t) id[i] = id[q];
		printf("%d %d\n",p,q);
	}
}

图示例
图中为执行合并操作后的结果，为了实现查找操作，只需测试指示数组中的元素是否相等，因此称为快速查找。而合并操作对于每对输入需要扫描整个数组。

性质：求解N个对象的连通性问题，如果执行M次合并操作，那么快速查找算法至少执行MN条指令。

对于每个合并操作，for循环迭代N次。每次迭代至少需要执行一次指令。

当M和N的值较小时，开销并不会很大，但是当有数百个对象，数亿个输入时，在用快速查找算法求解则不行。

下图是上图示例的图形化表示。
我们可以把某个对象看作它们所属集合的代表。所以这种表示中的对象之间的连接不必就是输入对的连接。