无名汉化组官网_什么是并查集

无名汉化组官网_什么是并查集永无乡包含 n 座岛,编号从 1 到 n ,每座岛都有自己的独一无二的重要度,按照重要度可以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛到达另一个岛。如果从岛 a 出发经过若干座(含 0 座)桥可以到达岛 b ,则称岛 a 和岛 b 是连通的。现在有两种操作:B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x 连通的所有岛中第 k 重要的是哪座岛,即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座,请你输出那

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

永无乡包含 n 座岛,编号从 1 到 n ,每座岛都有自己的独一无二的重要度,按照重要度可以将这 n 座岛排名,名次用 1 到 n 来表示。

某些岛之间由巨大的桥连接,通过桥可以从一个岛到达另一个岛。

如果从岛 a 出发经过若干座(含 0 座)桥可以到达岛 b ,则称岛 a 和岛 b 是连通的。

现在有两种操作:

B x y 表示在岛 x 与岛 y 之间修建一座新桥。
Q x k 表示询问当前与岛 x 连通的所有岛中第 k 重要的是哪座岛,即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座,请你输出那个岛的编号。
输入格式
第一行是用空格隔开的两个正整数 n 和 m ,分别表示岛的个数以及一开始存在的桥数。

接下来的一行是用空格隔开的 n 个数,依次描述从岛 1 到岛 n 的重要度排名。

随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi ,表示一开始就存在一座连接岛 ai 和岛 bi 的桥。

后面剩下的部分描述操作,该部分的第一行是一个正整数 q ,表示一共有 q 个操作,接下来的 q 行依次描述每个操作,操作的格式如上所述,以大写字母 Q 或 B 开始,后面跟两个不超过 n 的正整数,字母与数字以及两个数字之间用空格隔开。

输出格式
对于每个 Q x k 操作都要依次输出一行,其中包含一个整数,表示所询问岛屿的编号。

如果该岛屿不存在,则输出 −1。

数据范围
对于 20 的数据 n≤1000,q≤1000,
对于 100 的数据 n≤100000,m≤n,q≤300000

输入样例:
5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3
输出样例:
-1
2
5
1
2
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
struct Node{ 
   
    int s[2],v,p;
    int size,flag;
    int id;
    void init(int _v,int _p,int _id){ 
   
        v = _v,p  = _p,id = _id;
        size = 1;
    }
}tr[N];
int root[N],ctx;
int w[N];
int f[N];
void pushup(int u){ 
   
    tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
}
void pushdown(int u){ 
   
    return;
}
void rotate(int x){ 
   
    int y = tr[x].p,z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y,tr[y].p = x;
    pushup(y);
    pushup(x);
}
void splay(int x,int k,int r){ 
   
    while(tr[x].p != k){ 
   
        int y = tr[x].p,z = tr[y].p;
        if(z != k){ 
   
            if((tr[z].s[1] == y) ^ (tr[y].s[1] == x))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if(!k)root[r] = x;
}
int Find(int x){ 
   
    return f[x] = (x == f[x] ? f[x] : Find(f[x]));
}
int insert(int r,int v,int id){ 
           //r代表root[r]
    int u = root[r],p = 0;
    while(u)p = u,u = tr[u].s[v > tr[u].v];
    u = ++ ctx;
    if(p)tr[p].s[v > tr[p].v] = u;
    tr[u].init(v,p,id);
    splay(u,0,r);
    return u;
}
int get_th(int k,int r){ 
   
    int u = root[r];
    while(u){ 
          
        if(tr[tr[u].s[0]].size >= k)u = tr[u].s[0];
        else if(tr[tr[u].s[0]].size + 1 == k)return tr[u].id;
        else k -= tr[tr[u].s[0]].size + 1,u = tr[u].s[1];
    }
    return -1;
}
void dfs(int u,int b){ 
   
    if(tr[u].s[0])dfs(tr[u].s[0],b);
    if(tr[u].s[1])dfs(tr[u].s[1],b);
    insert(b,tr[u].v,tr[u].id);
}
int main(){ 
   
    int n,m;
    cin>>n>>m;
    int x,y;
    for(int i = 1;i <= n;i ++){ 
   
        cin>>x;
        root[i] = f[i] = i;
        tr[i].init(x,0,i);
    }
    ctx = n;
    for(int i = 0;i < m;i ++){ 
   
        cin>>x>>y;
        int a = Find(x),b = Find(y);
        if(a != b){ 
   
            if(tr[root[a]].size > tr[root[b]].size)swap(a,b);//把a插入到b中
            dfs(root[a],b);//合并
            f[a] = b;
        }
    }
    char c;
    cin>>m;
    for(int i = 0;i < m;i ++){ 
   
        cin>>c>>x>>y;
        if(c == 'Q'){ 
   
            int r = Find(x);
            if(y > tr[root[r]].size)cout<<-1<<endl;
            else cout<<get_th(y,r)<<endl;
        }
        else { 
   
            int a = Find(x),b = Find(y);
            if(a != b){ 
   
                if(tr[root[a]].size > tr[root[b]].size)swap(a,b);//把a插入到b中
                dfs(root[a],b);//合并
                f[a] = b;
            }
        }
    }
    return 0;
}
  1. 每一次合并不创建新节点
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Node{ 
   
    int s[2],v,p;
    int size,flag;
    int id;
    void init(int _v,int _p,int _id){ 
   
        v = _v,p  = _p,id = _id;
        size = 1;
    }
}tr[N];
int root[N],ctx;
int w[N];
int f[N];
void pushup(int u){ 
   
    tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
}
void pushdown(int u){ 
   
    return;
}
void rotate(int x){ 
   
    int y = tr[x].p,z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y,tr[y].p = x;
    pushup(y);
    pushup(x);
}
void splay(int x,int k,int r){ 
   
    while(tr[x].p != k){ 
   
        int y = tr[x].p,z = tr[y].p;
        if(z != k){ 
   
            if((tr[z].s[1] == y) ^ (tr[y].s[1] == x))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if(!k)root[r] = x;
}
int Find(int x){ 
   
    return f[x] = (x == f[x] ? f[x] : Find(f[x]));
}
int insert(int r,int x){ 
           //r代表root[r]
    int u = root[r],p = 0;
    while(u)p = u,u = tr[u].s[tr[x].v > tr[u].v];
    if(p)tr[p].s[tr[x].v > tr[p].v] = x;
    tr[x].p = p;
    splay(x,0,r);
    return u;
}
int get_th(int k,int r){ 
   
    int u = root[r];
    while(u){ 
          
        if(tr[tr[u].s[0]].size >= k)u = tr[u].s[0];
        else if(tr[tr[u].s[0]].size + 1 == k)return tr[u].id;
        else k -= tr[tr[u].s[0]].size + 1,u = tr[u].s[1];
    }
    return -1;
}
void dfs(int u,int b){ 
   
    if(tr[u].s[0])dfs(tr[u].s[0],b);
    if(tr[u].s[1])dfs(tr[u].s[1],b);
    insert(b,u);
}
int main(){ 
   
    int n,m;
    cin>>n>>m;
    int x,y;
    for(int i = 1;i <= n;i ++){ 
   
        scanf("%d",&x);
        root[i] = f[i] = i;
        tr[i].init(x,0,i);
    }
    ctx = n;
    for(int i = 0;i < m;i ++){ 
   
        scanf("%d %d",&x,&y);
        int a = Find(x),b = Find(y);
        if(a != b){ 
   
            if(tr[root[a]].size > tr[root[b]].size)swap(a,b);//把a插入到b中
            dfs(root[a],b);//合并
            f[a] = b;
        }
    }
    char c;
    cin>>m;
    for(int i = 0;i < m;i ++){ 
   
        cin>>c>>x>>y;
        if(c == 'Q'){ 
   
            int r = Find(x);
            if(y > tr[root[r]].size)printf("-1\n");
            else printf("%d\n",get_th(y,r));
        }
        else { 
   
            int a = Find(x),b = Find(y);
            if(a != b){ 
   
                if(tr[root[a]].size > tr[root[b]].size)swap(a,b);//把a插入到b中
                dfs(root[a],b);//合并
                f[a] = b;
            }
        }
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • 张正友相机标定法原理与实现「建议收藏」

    张正友相机标定法原理与实现「建议收藏」张正友相机标定法是张正友教授1998年提出的单平面棋盘格的相机标定方法。传统标定法的标定板是需要三维的,需要非常精确,这很难制作,而张正友教授提出的方法介于传统标定法和自标定法之间,但克服了传统标定法需要的高精度标定物的缺点,而仅需使用一个打印出来的棋盘格就可以。同时也相对于自标定而言,提高了精度,便于操作。因此张氏标定法被广泛应用于计算机视觉方面。…

  • 微信公众平台开发教程Java版(二) 接口配置

    微信公众平台开发教程Java版(二) 接口配置微信公众账号申请完成后,默认开启的是编辑模式。我们需要修改为开发模式。登陆微信公众平台》功能》高级功能先关闭编辑模式,再开启开发模式。申请成为开发者,如果是服务号,需要则会有开发者凭证信息如图如果是订阅号,则只显示服务器配置。下一步就是配置接口服务器了。在公众平台网站的高级功能–开发模式页,点击“成为开发者”按钮,填写U…

  • idea怎么集成git(idea中git的使用)

    一、IDEA集成git方法   首先idea集成git我们需要先下载一个小软件,gitbash 地址:https://git-scm.com/downloads 。下载好了之后直接下一步下一步傻瓜试安装。安装好后回在你指定的文件夹下有个git文件夹,文件结构如下:当然如果你对git命令比较熟悉,用这个软件就可以实现所有的git操作了。下面我们来集成进IDEA开发工具。打开I…

  • 什么叫做解析几何_笛卡尔心形函数

    什么叫做解析几何_笛卡尔心形函数解析几何是进行科学研究的重要的数学工具。比如说,要确定船只在大海中航行的位置,就要确立经纬度,这就需要精确的掌握夭体运行的规律;要改善枪炮的性能,就要精确地掌握抛射物体的运行规律。解决这些问题必须采用解析几何。因为它可以利用字母表示流动坐标,用方程刻划一般平面的曲线。解析几何的发明人就是伟大的数学家笛卡尔。笛卡尔15%年出生在法国,父亲是一位相当富有的律师。8岁时,父亲把他送进荃督教会学校读书。他…

    2022年10月10日
  • MATLAB实现线性插值interp1的功能

    MATLAB实现线性插值interp1的功能1.关于插值插值,它根据已知的数据序列(也可以理解为坐标中一连串离散的点),找到其中的规律;然后根据找到的这个规律,来对其中尚未有数据记录的点进数值的估计。2.关于线性插值线性插值是一种针对一维数据的插值方法,它根据一维数据序列中需要插值的点的左右邻近两个数据点来进行数值的估计。当然了它不是求这两个点数据大小的平均值(当然也有求平均值的情况),而是根据到这两个点的距离来分配它们的比重的。而对于一些边缘处的点也需要使用到外插:即通过找出最近的两个点,通过建立该两点之间的一元一次线性方程通过带入x即可以得

  • CSS3 opacity属性

    CSS3 opacity属性CSS3opacity属性记录设置一个div元素的透明度级别实现原理:opacity属性在实现的原理上极度类似于PS中的蒙版概念样式:div{opacity:0.5;}取值范围:0~1注意:IE8和早期版本支持另一种过滤器属性。像:filter:Alpha(opacity=50)属性说明默认值:1继承性:no(不继承)版本:CSS3属性:object.style.opacity问题1.如果父元素设置opacity属性,那么这个的所有子元素都

发表回复

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

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