菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
354
0

并查集 - 优化

原创
05/13 14:22
阅读数 96233

2017-07-28 17:27:41

writer:pprp

有两种优化方法:

  1. 路径压缩,在初始化某节点至根节点的路径后,将这条路径上所有的节点都设为根节点,这样将复杂度降为最低;
  2. 启发式合并,在合并两个结合的时候,将节点少的树合并到节点多的树上,也可以将高度小的树合并到高度大的树上;

题目:亲戚


代码如下:

#include <iostream>

using namespace std;

int N,M,Q;
int parent[1000];

int Find(int x)       //判断x所属集合
{
    int root = x;
    while(parent[root]>=0)    //找到根节点
        root = parent[root];
    while(root!=x)            //压缩路径,将该点直接
    {
        int tmp = parent[x];
        parent[x]= root;
        x = tmp;
    }
    return root;
}

void Merge(int a,int b)     //较小的树成为较大的树的子树
{
    int pa = Find(a);
    int pb = Find(b);
    if(pb < pa)
        swap(pb,pa);
    if(pa!=pb)
        parent[pb] = pa;
}

int main()
{
    int i,a,b;
    cin >> N >> M >> Q;

    for(i=1; i<=N; i++)
    {
        parent[i] = -1;
    }
    for(i=1; i<=M; i++)
    {
        cin >> a >> b;
        if(Find(a)!=Find(b))
            Merge(a,b);
    }
    for(i=1; i<=Q; i++)
    {
        cin >> a >> b;
        if(Find(a)==Find(b))
            cout <<"Yes"<<endl;
        else
            cout <<"No"<<endl;
    }

    return 0;
}

 

发表评论

0/200
354 点赞
0 评论
收藏
为你推荐 换一批