并查集(种类并查集,带权并查集)

这篇具有很好参考价值的文章主要介绍了并查集(种类并查集,带权并查集)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
 

题目描述

动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B,B吃C,C吃A。

现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。

有人用两种说法对这N个动物所构成的食物链关系进行描述:

第一种说法是“1 X Y”,表示X和Y是同类。

第二种说法是“2 X Y”,表示X吃Y。

此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

1) 当前的话与前面的某些真的话冲突,就是假话;

2) 当前的话中X或Y比N大,就是假话;

3) 当前的话表示X吃X,就是假话。

你的任务是根据给定的N(1≤N≤50,000)和K句话(0≤K≤100,000),输出假话的总数。

输入描述:

第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。

输出描述:

只有一个整数,表示假话的数目。

种类并查集

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n;
ll fa[150004];
ll find(ll x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(ll a,ll b)
{
    a=find(a),b=find(b);
    fa[a]=b;
}
void solve()
{
    ll n,k;
    cin>>n>>k;
    ll ans=0;
    for(ll i=1;i<=150003;i++)
    {
        fa[i]=i;
    }
    ll op,x,y;
    for(ll i=0;i<k;i++)
    {
        cin >> op >> x >> y;
        if (x > n || y > n || (op == 2 && x == y)) {
            ans++;
            continue;
        }
        if (op == 1) {
            if (find(x) == find(y + n) || find(x) == find(y + 2 * n)) {
                ans++;
            }
            else {
                merge(x, y);
                merge(x + n, y + n);
                merge(x + 2 * n, y + 2 * n);
            }
        }
        else {
            if (find(x) == find(y) || find(x) == find(y + 2 * n)) {
                ans++;
            }
            else {
                merge(x, y + n);
                merge(x + n, y + 2 * n);
                merge(x + 2 * n, y);
            }
        }
    }
    cout<<ans<<'\n';
}
    int main()
   {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    while(t--)
    solve();
    return 0;
    }

带权并查集文章来源地址https://www.toymoban.com/news/detail-667518.html

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n;
ll fa[50004];
ll re[50004];
ll find(ll x)
{
    if(x!=fa[x])
    {
        ll t=fa[x];
        fa[x]=find(fa[x]);
        re[x]=(re[x]+re[t])%3;
    }
    return fa[x];
}
void merge(ll a,ll b,ll k)//012,同类,捕食,被捕食
{
    ll x=find(a),y=find(b);
    if(a!=b)
    {
        fa[x]=y;
        re[x]=(k+re[b]-re[a]+3)%3;
    }
}
void solve()
{
    for(ll i=1;i<=50002;i++)
    {
        fa[i]=i;
        re[i]=0;
    }
    ll n,k;
    cin>>n>>k;
    ll nums=0;
    for(ll i=1;i<=k;i++)
    {
        ll d,x,y;
        cin>>d>>x>>y;
        ll a=find(x),b=find(y);
        if(x>n||y>n||(d==2&&x==y))
        {
            nums++;
        }
        else if(d==1)
        {
            if(a!=b)
            {
                merge(x,y,0);
            }
            else if(re[x]!=re[y]){
                nums++;
            }
       }
       else
       {
             if(a!=b)
            {
                merge(x,y,1);
            }
            else if((re[x]-re[y]+3)%3!=1){
                nums++;
            }
      }
        
    }
    cout<<nums;
}
    int main()
   {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    while(t--)
    solve();
    return 0;
    }

到了这里,关于并查集(种类并查集,带权并查集)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构---并查集

    这里可以使用生活中的一个例子来带着大家理解并查集,大家在上学的过程中肯定会发现一种现象,在开学之前大家谁也不认识谁每个人都是一个小团体,可是开学之后因为座位旁边有一个同桌,所以开学没多久你和同桌就会互相认识并且开心的玩在一起,那么这时就是两个

    2024年02月15日
    浏览(40)
  • 高阶数据结构 ——— 并查集

    并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。 并查集通常用森林来表示,森林中的每棵树表示一个集合,树中的结点对应一个元素。 说明一下: 虽然利用其他数据结构也能完成不相交集合的合并及查询,但在数据量极大的情况下,其耗费的时

    2024年02月03日
    浏览(52)
  • 【数据结构】并查集

    并查集是简单的数据结构,学会并查集,为图打好基础。 是树状的数据结构,用于处理相交集合的合并与查询 通常用森林表示,一片森林表示一个集合 并查集一般需要完成 查找元素属于哪个集合 查看两个元素是否属于同一个集合 将两个集合归并成一个集合 集合的个数 假

    2024年02月19日
    浏览(35)
  • 【数据结构】--并查集

    目录 一、概念 ​编辑 二、应用场景--“连接”问题(属于同一Qu 三、实现思路  四、如何存储数据 五、定义接口 1.初始化(init) 2.其他 isSame() 六、抽象类 六、Quick Find【v1 所在集合的所有元素都指向 v2 的根节点】 1.Union 1.Union图解 2.注意点:  3.代码实现 2.find  1.find图

    2023年04月09日
    浏览(31)
  • 数据结构详细笔记——并查集

    集合:将各个元素划分为若干个互不相交的子集的集合 森林是m(m=0)棵互不相交的树的集合 优化思路:在每次Union操作构建树的时候,尽可能让树不长高 ①用根结点的绝对值表示树的结点的总数 ②Union操作,让小树合并到大树 优化思路:先找到根结点,再将查找路径上所有结

    2024年02月06日
    浏览(38)
  • 数据结构之并查集

    并查表原理是一种 树型的数据结构 ,用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林(parent),树的根节点唯一标识了一个集合,我们只要找到了某个元素的树根,就能确定它在哪个集合里。这类问题的抽象数据类型称为并查集(uni

    2024年02月12日
    浏览(36)
  • 【数据结构与算法】并查集

    并查集是一个树形结构,所谓的并查,就是 当我们有了一个节点,我们就能知道这个节点属于哪个集合 。 举个例子理解以下:战国时期有很多国家,它们会互相打仗,那么现在有两个互相不认识的人,如何知道对方是敌是友呢? 现在有一种方法:每个国家都有一个大王,我

    2023年04月15日
    浏览(36)
  • 算法与数据结构(九)--并查集

    1.处理对象:Disjoint Set,即“不相交集合”。 在一些应用问题中,需将n个不同的元素划分成一组不相交的集合。开始时,每个元素自成一个单元素集合,然后按一定顺序将属于同一组元素的集合合并。其间要反复用到查询某个元素属于哪个集合的运算。适合于描述这类问题的

    2024年02月10日
    浏览(40)
  • 【数据结构】| 并查集及其优化实现

    以一个直观的问题来引入并查集的概念。 亲戚问题:有一群人,他们属于不同家族,同一个家族里的人互为亲戚,不同家族的人不是亲戚。随机指定两个人,问他们是否有亲戚关系。 以下图3个不相交的集合表示 3 个家族,当询问两个人是否有亲戚关系时,也就是问两个元素

    2024年02月09日
    浏览(37)
  • 数据结构(八):并查集详解 (多图+动图)

    目录 一、什么是并查集 二、并查集的存储结构 三、并查集的基本操作 (一)初始化 (二)Find操作 (三)Union操作 四、并查集的优化 (一)Union操作优化(小树并入大树) (二)Find操作优化(压缩路径)         并查集的逻辑结构是一个包含N个元素的 集合 ,如图:

    2024年02月03日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包