首页 > 代码库 > [SOJ]连通性问题
[SOJ]连通性问题
Description
关系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可由之前数对的连通关系得到，故不做输出。
Input
输入共有m行(0<=m<=1000000),每行一个数对，数对的数字之间以1个空格分隔；数对的数字为0或n=100000以内的自然数。
Output
输出包含过滤之后的数对序列。每行输出一个数对，数对的数字之间以1个空格分隔。
Sample Input
Copy sample input to clipboard3 4 4 9 8 0 2 3 5 6 2 9 5 9 7 3 4 8 5 6 0 2 6 1
Sample Output
3 4 4 9 8 0 2 3 5 6 5 9 7 3 4 8 6 1
//在本题中要删去所有具有连通性的结点，而具有连通性的结点的性质是
//在图中具有相同的祖先，则我们只要通过判断两个结点是否存在相同的祖先
//即可判断是否需要删去，最直接的做法是每插入一对结点，DFS或BFS，判断是否搜索到相同的点
//但这样做法时间复杂度太大，在一开始时就让每个结点指向自己的祖先结点
#include<iostream>
using namespace std;
const int MAX = 1000005;
int father[MAX];
int find(int num) {return ( num==father[num] ? num : (father[num]=find(father[num])) );}
int main()
{
int m;
for(int i=0;i<MAX;i++)
father[i]=i;
int point1, point2;
while(cin>>point1>>point2)
{
if(find(point1)!=find(point2))
{
cout<<point1<<" "<<point2<<endl;
father[find(point1)]=father[find(point2)];
}
}
return 0;
}
[SOJ]连通性问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。