并查集例题_并查集算法

并查集例题_并查集算法E – 带删除并查集 UVA – 11987 Almost Union-Find

大家好,又见面了,我是你们的朋友全栈君。

UVA – 11987 Almost Union-Find

I hope you know the beautiful Union-Find structure. In this problem, you’re to implement something similar, but not identical. The data structure you need to write is also a collection of disjoint sets, supporting 3 operations: 1 p q Union the sets containing p and q. If p and q are already in the same set, ignore this command. 2 p q Move p to the set containing q. If p and q are already in the same set, ignore this command. 3 p Return the number of elements and the sum of elements in the set containing p. Initially, the collection contains n sets: {1}, {2}, {3}, . . . , {n}. Input There are several test cases. Each test case begins with a line containing two integers n and m (1 ≤ n, m ≤ 100, 000), the number of integers, and the number of commands. Each of the next m lines contains a command. For every operation, 1 ≤ p, q ≤ n. The input is terminated by end-of-file (EOF). Output For each type-3 command, output 2 integers: the number of elements and the sum of elements. Explanation Initially: {1}, {2}, {3}, {4}, {5} Collection after operation 1 1 2: {1,2}, {3}, {4}, {5} Collection after operation 2 3 4: {1,2}, {3,4}, {5} (we omit the empty set that is produced when taking out 3 from {3}) Collection after operation 1 3 5: {1,2}, {3,4,5} Collection after operation 2 4 1: {1,2,4}, {3,5} Sample Input 5 7 1 1 2 2 3 4 1 3 5 3 4 2 4 1 3 4 3 3 Sample Output 3 12 3 7 2 8

并查集例题_并查集算法

并查集例题_并查集算法

题意是:1~n,n个数,初始每个数独自作为一个集合,然后进行m次操作。操作有三种:1 p q :把 p 所在的集合合并到 q 所在的集合

                                             2 p q :把 p 从 p 的集合中拿出,放到 q 的集合里

                                        3 p    :输出 p 所在的集合的元素个数和元素之和

思路:ma[x]=y 代表x在编号为y的集合里,fa[y]=z 代表编号为y的集合编号为z的集合同一连通分支(本来也是集合,但都说集合不太好分辨,并查集的部分就说连通分支吧)内(把集合当作个体来并查集),再用两个数组分别记录连通分支 i 内的数字的个数cou和数字的和sum

          这样的话对于1操作:fa[fx]=fy(fx是x所在的连通分支,fy是y所在的连通分支),//合并fx和fy

             cou[fy]+=cou[fx];  

            sum[fy]+=sum[fx]; 

             cou[fx]=0;  //清空fx

             sum[fx]=0; 

           2操作:cou[fx]–;

            cou[fy]++;
            sum[fy]+=x;
            sum[fx]-=x;
            ma[x]=ma[y];

        3操作:cou[fx] sum[fx]

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#define Twhile() int T;scanf("%d",&T);while(T--)
#define clc(a,b) memset(a,b,sizeof(a))
#define fora(i,a,b) for(i=a;i<b;i++)
#define fors(i,a,b) for(i=a;i>b;i--)
#define fora2(i,a,b) for(i=a;i<=b;i++)
#define fors2(i,a,b) for(i=a;i>=b;i--)
#define PI acos(-1.0)
#define eps 1e-6
#define INF 0x3f3f3f3f

typedef long long LL;
typedef long long LD;
using namespace std;
const int maxn= 100000+11;
map<int,int>ma;
int cou[maxn],sum[maxn];
int fa[maxn];
int n,m;
void init()
{
    ma.clear();
    int i;
    fora2(i,1,n)
    {
        fa[i]=i;
        cou[i]=1;
        sum[i]=i;
        ma[i]=i;
    }
}
int findx(int x)
{
    if(x==fa[x])return x;
    return fa[x]=findx(fa[x]);
}
int main()
{
    int kcase=0;
    while(~scanf("%d%d",&n,&m))
    {
        init();
        while(m--)
        {
            int op;
            scanf("%d",&op);
            if(op==3)
            {
                int x;
                scanf("%d",&x);
                int fx=findx(ma[x]);
                printf("%d %d\n",cou[fx],sum[fx]);
                continue;
            }
            int x,y;
            scanf("%d%d",&x,&y);
            int fx=findx(ma[x]),fy=findx(ma[y]);
            if(fx==fy)continue;
            if(op==1)
            {
                //合并连通分支fx和fy
                fa[fx]=fy;
                cou[fy]+=cou[fx];
                sum[fy]+=sum[fx];
                //清空fx
                cou[fx]=0;
                sum[fx]=0;
                continue;
            }
            //把x从集合ma[x]拿出来
            sum[fx]-=x;
            cou[fx]--;
            //把x放到集合ma[y]
            ma[x]=ma[y];
            cou[fy]++;
            sum[fy]+=x;
            
            

        }
    }
    return 0;
}

 

 

转载于:https://www.cnblogs.com/107acm/p/9430924.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107379.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • SQL SERVER插件之SQLPrompt 激活使用

    SQL SERVER插件之SQLPrompt 激活使用如有不懂,可以关注麒琳技术栈,欢迎在线咨询

  • CentOS 6.5 & CentOS 7 rpm安装ftp服务端与ftp客户端「建议收藏」

    CentOS 6.5 & CentOS 7 rpm安装ftp服务端与ftp客户端「建议收藏」一、rpm安装ftp服务端1、查看是否安装vsftprpm-qa|grepvsftpd如果出现vsftpd,说明已经安装vsftp2、下载vsftpd:我这里下载的是vsftpd-2.2.2-24.el6.x86_64.rpm3、安装vsftpdrpm-ivhvsftpd-2.2.2-24.el6.x86_64.rpm4、测试是否安装成功servicevsftp…

    2022年10月21日
  • centos7查看文件系统类型_linux如何查看文件格式

    centos7查看文件系统类型_linux如何查看文件格式CentOS7查看磁盘文件系统格式(转载)

  • 舆情分析系统技术解决方案及作用论文_网络舆情解决方案

    舆情分析系统技术解决方案及作用论文_网络舆情解决方案网络舆情分析工作的开展最先需要做好的就是网络舆情的搜集工作,由于互联网信息内容庞杂多样,舆情信息搜集起来困难,所以要进行舆情分析更是难上加难。但若舆情信息收集的不全,就极易导致舆情分析不正确。那么,到底舆情分析工作要怎么做呢?针对此问题,提供了以下舆情分析系统技术解决方案,供各位参考。在了解方案的前,先来说说为什么要采用舆情分析系统进行监测分析。一、使用舆情分析系统进行监测分析的意义网络信息化时代,信息数据量庞大,若一味采用人工进行舆情信息分析,容易出现收集的舆情不全、舆情分析不正确等问题。而通过利用

  • .tex文件中通过空行实现LaTeX换行输出

    .tex文件中通过空行实现LaTeX换行输出【LaTeX换行输出代码示例】\documentclass{article}\begin{document} Happy\TeXing. Hello\LaTeX. Happy\TeXing. Hello\LaTeX.\end{document}【输出结果】

  • python函数可以按照参数名称方式传递参数_python字符串作为函数参数

    python函数可以按照参数名称方式传递参数_python字符串作为函数参数首先还是应该科普下函数参数传递机制,传值和传引用是什么意思?函数参数传递机制问题在本质上是调用函数(过程)和被调用函数(过程)在调用发生时进行通信的方法问题。基本的参数传递机制有两种:值传递和引用传递。值传递(passl-by-value)过程中,被调函数的形式参数作为被调函数的局部变量处理,即在堆栈中开辟了内存空间以存放由主调函数放进来的实参的值,从而成为了实参的一个副本。值传递的特点是被调函数…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号