首页 > 其他分享 >并查集 - 亲戚

并查集 - 亲戚

时间:2023-10-23 09:12:12浏览次数:35  
标签:merge int res 查集 亲戚 fa find

 

#include<iostream>
#include<vector>
using namespace std;

vector<int> fa{ -1 };
int find(int i) {
    if (fa[i] != i) fa[i] = find(fa[i]);
    return fa[i];
}

void merge(int i, int j) {
    fa[find(i)] = find(j);
}

int main() {
    int n, m, p;
    cin >> n >> m >> p;

    for (int i = 1; i <= n; i++) fa.push_back(i);
    for (int i = 0, a, b; i < m; i++) {
        cin >> a >> b;
        merge(a, b);
    }
    string res;
    for (int i = 0, a, b; i < p; i++) {
        cin >> a >> b;
        res += (find(a) == find(b) ? "Yes\n" : "No\n");
    }
    cout << res;
    return 0;
}

 

标签:merge,int,res,查集,亲戚,fa,find
From: https://www.cnblogs.com/xlege/p/17781621.html

相关文章

  • [HNOI2010] 平面图判定-平面图性质、带权并查集/2-sat
    [HNOI2010]平面图判定-平面图性质、带权并查集/2-sathttps://www.luogu.com.cn/problem/P3209题意:给一张\(n\)个点,\(m\)条边的哈密顿图,并且哈密顿回路已知,问是否是平面图,\(T\)组询问。\(1\leqT\leq100,1\leqn\leq200,1\leqm\leq10^4\)。转换挺奇妙的。极大平面......
  • 关于并查集的感受
    什么情况下2个节点还没加入一个集合就已经在一个集合了?就说明如果把这2个节点画进图里连起来,那么一定构成了一个环。举个简单的栗子 对于join函数,只要加入了2个节点,那么至少这两个节点就构成了1个集合,如果还没加入它们就以及有同一个根节点了那么就说明对应的图里存在环,如果......
  • 种类并查集
    P1892[BOI2003]团伙如果你wa,可能是合并的顺序出错[1,n]表示朋友,[n+1,2*n]表示敌人如果a,b是朋友,直接合并a,b如果a,b是敌人:1.合并a+n和b,a的敌人是b的朋友2.合并a和b+n,b的敌人是a的朋友点击查看代码#include<bits/stdc++.h>usingnamespacestd;intf[20005];intd[20......
  • 并查集
    并查集的原理来自百度百科并查集,在一些有N个元素的集合应用问题中,我们通常是在开始的时候让每个元素构成单个元素的集合,然后按一定顺序讲属于同一组的元素所在集合合并,期间要反复查询一个元素在哪个集合中。描述改问题的抽象数据结构为并查集。并查集是一种树型的数据结构,用于处理......
  • 并查集学习指南
    前置芝士并查集思想[find][python]#pythonwhiledeffind(x:int)->int: whilex!=fa[x]: x=fa[x]=fa[fa[x]] returnx#python递归deffind(x:int)->int: iffa[x]!=x: fa[x]=find(fa[x]) returnfa[x][c++]//c++whilelambda/*function<int(int)>fi......
  • [算法分析与设计] 3. 并查集分析与反阿克曼函数
    Union-Find问题:给定\(n\)个元素,最初每个元素在一个集合中,有两种操作,union表示合并两个集合,find表示查询某个特定元素所在的集合。并查集是一种数据结构。其为每个集合寻找一个代表元,代表元可以是任意的,也可以随操作变化,但需要满足任何时刻一个集合的代表元是确定且唯一的。......
  • 并查集
    并查集如果有一个关系网,我们需要建立两点之间的关系,如果仅用一维链表,则有可能无法考虑到两点同为一点“儿子”的情况,则我们需要建立一个方式,从而直接对比两点“祖父”。一.递归查询intfind(intx){ if(fa[x]==x)returnx;//只有祖父自环,如果他也自环,则找到父节点 ......
  • 并查集的实现【学习算法】
    并查集的实现【学习算法】前言版权推荐并查集的实现最后前言2023-9-2614:38:02以下内容源自《【学习算法】》仅供学习交流使用版权禁止其他平台发布时删除以下此话本文首次发布于CSDN平台作者是CSDN@日星月云博客主页是禁止其他平台发布时删除以上此话推荐算法讲解056【必备】并......
  • 并查集
    基本的并查集OI-wikiLink并查集,一种用于管理元素所属集合的数据结构,形如一片森林,同一棵树内的元素所属同一集合,不同树内的元素不属于同一集合。将并查集拆分一下。并,合并;查,查询;集,处理的是集合相关内容。所以并查集一共有两种操作:合并两元素对应集合、查询某元素所属集合(查......
  • 数据结构-并查集
    并查集的使用范围:1.合并集合2.查询两元素是否属于同一集合   高级用法:  3.进行集合划分<带权并查集>  4.连通块块数查询&块内元素个数统计<连通图>  5.撤销合并<可持久化并查集>//本文暂不涉及,我还不会并查集基本操作:#definerep(i,n)for(int......