首页 > 其他分享 >并查集

并查集

时间:2023-02-22 19:24:05浏览次数:44  
标签:关系 朋友 查集 int 集合 敌人

并查集

序言:我们大家都是好朋友

并查集是一种维护关系的数据结构

新手所学的并查集都是维护朋友关系的并查集

朋友的朋友是朋友

我们可以将变成朋友的点连到同一个集合中

模板

//并查集
const int N=2e5+10;
int p[N];
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

蒙尘:你讨厌我我也讨厌你

一般的并查集只能够维护朋友关系

但是有些题目需要维护敌人关系

此时有

敌人的敌人是朋友

根据这条属性,我们可以将并查集拓展

使其能够维护敌人关系

我们可以单独开辟出两个集合

如果 \(a\) 和 \(b\) 是敌人,那么就将 \(a\) 和 \(b+n\) 将 \(a+n\) 和 \(b\) 合并到一个集合中

如果 \(a\) 和 \(c\) 是敌人,那么就将 \(a\) 和 \(c+n\) 将 \(a+n\) 和 \(c\) 合并到一个集合中

那么我们可以发现

\(b\) 和 \(c\) , \(b+n\) 和 \(c+n\) 都合并到一个集合中了

由此便实现了敌人的敌人是朋友的属性

例题:P1892BOI2003]团伙

终章:原来你一直讨厌我吗

上面讲的敌人的属性是建立在敌对关系是双向的基础上

那如果敌对关系是单向的呢

那就要开三个集合

考虑在不同种类的并查集中合并的意义,表达了 他们是敌人 这个关系

具体实现请类比蒙尘篇

例题:P2024[NOI2001]食物链https://www.luogu.com.cn/problem/P2024)

标签:关系,朋友,查集,int,集合,敌人
From: https://www.cnblogs.com/liangqianxing/p/17145558.html

相关文章

  • 浅谈一类多重传递关系的并查集问题
    首先解释一下什么叫“多种传递关系”:普通的并查集只能维护“朋友的朋友是朋友”,而面临“敌人的敌人是朋友”的情况十分乏力,多种传递关系即指“敌人的敌人是朋友”类情况。......
  • A - 并查集【2022级专题三图论课后练习】
    A-并查集思路模板注意01串的处理代码点击查看代码#include<iostream>usingnamespacestd;#defineXfirst#defineYsecondtypedefpair<int,int>pii;......
  • 【DFS&并查集】岛屿数量
    经典的dfs/bfs问题,给一个起点开始搜索,满足条件则继续调用dfs/bfs从没有访问过的某个陆地出发,将所有能到达的陆地的状态都记录为已访问。下次出发不从已访问的陆地出发,每次......
  • C - Roads and Libraries HackerRank - torque-and-development 【 并查集 】
    C-RoadsandLibraries HackerRank-torque-and-development 题意:给一堆点与点之间有没有边,在某一些地方建图书馆,最后让每个城市都可以到达有图书馆的地方,每个点......
  • Codeforces Round #851 (Div. 2)-F. XOR, Tree, and Queries-树、异或、并查集
    题目:https://codeforces.com/contest/1788/problem/F题解:(首先他和线性基没什么瓜系)想这个问题大概可以分成几个部分:1、很自然地考虑记\(p_x\)表示从根节点走到x路径......
  • 「AcWing学习记录」并查集
    并查集1.将两个集合合并2.询问两个元素是否在一个集合当中时间复杂度近乎O(1)基本原理每个集合用一棵树来表示。树根的编号就是整个集合的编号,每个节点存储它的父节点......
  • 并查集
    一、什么是并查集什么是并查集?字面意思把一堆东西  合并  、  查找二、并查集讲解前置知识点1.可以把并查集的实现理解为在合并几棵树2.需要用到fa数组,fa[i......
  • 并查集
    并查集大佬笔记如下:通俗易懂https://zhuanlan.zhihu.com/p/93647900并查集是什么?主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:合并:把......
  • 【YBT2023寒假Day8 C】图论题(图论)(并查集)(线段树合并)
    图论题题目链接:YBT2023寒假Day8C题目大意给你一个无向图,然后你会一直操作直到无法操作,每次找出一个满足条件的三元组(a,b,c),满足a<b<c,a,b与a,c之间有边,b,c之间没......
  • 2021 年百度之星·程序设计大赛 - 初赛二 1003 魔怔(并查集,联通性,欧拉回路)
    problemsolution发现除了起点和终点,剩下所有点周围的边都会被恰经过偶数次,所以这些点初始连向了偶数条白边。考虑由白边连接形成的图,每个连通块中度数为奇数的点一定为偶数......