连通性问题

题目描述
关系R具有对称性和传递性。数对p q表示pRq,p和q是0或自然数,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

其中数对2 9和0 2可由之前数对的连通关系得到，故不做输出。

输入描述
输入共有m行(0<=m<=1000000),每行一个数对，数对的数字之间以1个空格分隔；数对的数字为0或n=100000以内的自然数。

输出描述
输出包含过滤之后的数对序列。每行输出一个数对，数对的数字之间以1个空格分隔。

输入样例

3 4
4 9
8 0
2 3
5 6
2 9
5 9
7 3
4 8
5 6
0 2
6 1

输出样例

3 4
4 9
8 0
2 3
5 6
5 9
7 3
4 8
6 1

参考答案

#include <iostream>
using namespace std;

const int maxn = 1000001;
int p[maxn];

int find(int x)
{
    //查找过程顺带进行了路径压缩
    return (x == p[x]) ? x : (p[x] = find(p[x]));
}
void merge(int x,int y){
    p[y] = x;
}

int main()
{
    for (int i = 0; i < maxn; i++)//初始化并查集
    {
        p[i] = i;
    }
    int num1, num2;
    while (cin >> num1 >> num2)
    {
        if (find(num1) != find(num2))//数对中的二者不在同一个集合中才输出
        {
            cout << num1 << " " << num2 << endl;//输出操作
            merge(find(num1),find(num2));//做合并操作
        }
    }
}

在本题中要删去所有具有连通性的结点，而具有连通性的结点的性质是：在图中具有相同的祖先。
则我们只要通过判断两个结点是否存在相同的祖先，即可判断是否需要删去。
最直接的做法是每插入一对结点，DFS（深度优先搜索）或BFS（广度优先搜索），判断是否搜索到相同的点。但这样做法时间复杂度太大，在一开始时就让每个结点指向自己的祖先结点可能更好。

参考资料
知乎： 算法学习笔记(1) : 并查集
CSDN：#sicily#1000.连通性问题
博客园：[SOJ]连通性问题