欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Luogu [P3367] 模板 并查集

程序员文章站 2022-04-03 23:36:24
【模板】并查集 题目详见:[【P3367】【模板】并查集] (https://www.luogu.org/problemnew/show/P3367) 这是一道裸的并查集题目(要不然叫模板呢) 废话不多说进入正题: 并查集通过一个一维数组来实现,本质上是维护一个森林。刚开始的时候,森林里的每一个结点 ......

【模板】并查集

 

题目详见:[【P3367】【模板】并查集] (https://www.luogu.org/problemnew/show/P3367)

这是一道裸的并查集题目(要不然叫模板呢) 废话不多说进入正题:

并查集通过一个一维数组来实现,本质上是维护一个森林。刚开始的时候,森林里的每一个结点都是一个集合(也就是只有一个结点的树),之后根据题意,逐渐将一个个集合合并(也就是合并成一棵大树)。之后寻找时不断查找父节点,当查找到父结点为本身的结点时,这个结点就是祖宗结点。合并则是寻找这两个结点的祖宗结点,如果这两个结点不相同,则任意将其中一边的集合作为另一边集合的子集。

 

AC代码:

#include<iostream>
using namespace std;
int n/*n个元素*/,m/*m个操作*/,f[10001]/*第i个人的祖宗为f[i]*/;
int find(int x)            //找祖宗(※※重点) 
{
    if(f[x]==x)            //若自己的祖宗为自己 
      return f[x];          
    else                     
      return f[x]=find(f[x]);//路径压缩(※※难点):把递归过程中遇到的结点的祖宗结点也直接修改了 
}
void hebing(int x,int y)       //合并操作
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)                 //(其实这一步可有可无,因为之前已经判断过了) 
      f[fx]=fy;                //x的祖宗  的父亲  为y的祖宗 
    return;
} 
int main()
{
    cin>>n>>m;    //读入
    for(int i=1;i<=n;i++)
    f[i]=i;                //初始化:n个数,每个数祖宗为自己 
    for(int i=1;i<=m;i++)  //依次读入m个操作要求
    {
        int z,x,y;
        cin>>z>>x>>y;
        if(z==2)           //执行查询操作 
        {
            if(find(x)==find(y)) //如果两个人为同一个祖宗,则在一个集合 (※※重点)
              cout<<"Y"<<endl;
            else           //否则不在一个集合 
              cout<<"N"<<endl;
        }
        else               //执行合并操作 
          hebing(x,y); 
    } 
    return 0;
}