这是我在阅读<<算法1-4（C++实现）——基础，数据结构，排序和搜索（第三版）>>
([美]Robert Sedgewick 著， 张铭泽 赵剑云 梁勇等 译  中国电力出版社)
时整理的读书笔记,现在贴出来,希望能给初学者一些启发.
/*
  Name:  连通问题
  Copyright: 
  Author: 
  Date: 25-11-06 21:59
  Description: 连通问题 
  假设有一个整数对的序列，每个整数代表某个类型的一个对象，p-q对表示"p连接到q"，
  即p和q之间连通。假设连通关系具有传递性--如果p与q连通，q与r连通，那么p与r连通。
  我们的目标是写一个过滤出那些不在集合中的对的程序：输入p-q对时，
  如果已输入的对的集合中没有隐含这样的对（通过连通关系的传递性），那么程序将输出该对。
  如果前面输入的对隐含了p与q的连通，那么程序将忽略p-q，准备输入下一对。
输入输出示例如下：
输入    输出        隐含
3-4        3-4
4-9        4-9
8-0        8-0
2-3        2-3
5-6        5-6
2-9        不输出        2-3-4-9
5-9        5-9
7-3        7-3
4-8        4-8
5-6        不输出        5-6
0-2        不输出        0-8-4-3-2
6-1        6-1
1-2        不输出        1-6-5-9-4-3-2

*/

/*
连通问题
该程序读入一组介于0和N之间（包含0，但不包含N）的非负整数对，p-q对表示p和q连通，
输出那些目前尚未连通的输入对。它使用了数组id，每个对象在数组中都有一项，
当且仅当p与q连通时id[p]和id[q]相等。为简化问题，我们定义N为编译时常量，
当然也可以通过输入确定N，再动态地分配id数组。
*/
#include <iostream>

using namespace std;

const int N = 9000;

bool IsConnected_1(int id[], int p, int q);
bool IsConnected_2(int id[], int p, int q);
bool IsConnected_3(int id[], int p, int q);
bool IsConnected_4(int id[], int p, int q);
bool IsConnected_5(int id[], int p, int q);
bool IsConnected_6(int id[], int p, int q);

int main()  
{
    int id[N];
    for (int i=0; i<N; i++)
        id[i] = i;
        
    int p, q;
    
    //////////此部分由用户输入数据测试代码/////////////////
//    while (cin >> p >> q)
//    {    
//        if (!IsConnected_6(id, p, q))
//            cout << p << "-" << q << endl;
//            
//        for (int i=0; i<N; i++)
//            cout << id[i] << " ";
//        cout << endl;
//    }
///////////////////////////////////////////////
    /////////此部分由计算机产生大量随机数测试代码//////////////////
    const int max = 80000;
    int i = 0;
    while (i < max)
    {
        p = rand() % N;
        q = rand() % N;
        if (p == q)
            continue;
            
    //    cout << p << "-" << q << " :   ";
        
        if (!IsConnected_6(id, p, q));
        //    cout << p << "--" << q << endl;
    //    else
//            cout << endl;
        
        i++;
    }
    
    cout << clock() << endl;
    /////////////////////////////////////  
    getchar();
    return 0;
}
/*
经过大量数据的测试得知： 
IsConnected_1受N的影响较大，而受max的影响很小。
IsConnected_2和IsConnected_3的时间复杂度在各种情况下均相当，均受max的影响较大，而受N的影响很小。
IsConnected_4，IsConnected_5和IsConnected_6的时间复杂度相当，其中IsConnected_4最好，
IsConnected_5其次，IsConnected_6较差，但它们都比前三者要快很多。三者均受max的影响较大，而受N的影响很小。
IsConnected_4与IsConnected_5的比较说明路径被压缩以后，每棵树的高度都很小，没有必要花费精力去记录权值。
带权的压缩路径算法 因为要增加部分代码和一个保存节点计数的数组，反而变慢了。
IsConnected_4与IsConnected_6的比较说明在压缩路径时，没有必要把所有的节点都指向根节点，
这样虽然实现了快速查找，但合并的时间增多。
所以 等分路径压缩的快速合并算法 是一种较为合理的算法。 
*/