「so easy」so easy（并查集）

so easy

代码实现

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
unordered_map<int, int> m;
int find(int x)
{
	if(!m.count(x))
		return x;
	else
		return m[x]=find(m[x]);
} 
int main() {
    int n, q;
    scanf("%d%d",&n,&q);
    int op, x;
    while (q--)
	{
        scanf("%d%d",&op,&x);
        if (op==1){
            m[x]=find(x+1);
        }else{
            int ans=find(x);
            if(ans>n) ans=-1;
            printf("%d\n",ans);
        }
    }
    return 0;
}

涉及知识盲区，积累一下

unordered_map

//需要头文件
#include<unordered_map>

map/unordered_map是一个关联容器，它按照特定顺序存储由键值和映射值的组合形成的元素；

在映射中，键值通常用于排序和唯一标识元素，而映射值存储与此键关联的内容。

map容器通常比unordered_map容器慢，以便通过键访问单个元素，但它们允许根据子集的顺序直接迭代子集。在该映射值地图可以直接通过使用其相应的键来访问括号运算符（（操作符[] ）。映射通常如实施二叉搜索树。

用insert插入

返回容器可以作为内容保存的最大元素数

m.max_size()

返回容器中的元素数量

m.size()

返回bool值，判断是否为空

m.empty()

这个end()返回的是最后一个元素的下一个地址

m.end()

从地图容器中移除单个元素或一系列元素

erase

交换两个同类型容器的内容，尺寸可以不同。

swap

删除所有元素，使容器的大小为 0

clear

计数，但是map中本身key就是唯一的，所以包含这返回1，不包含则返回0

count

map与unordered_map的区别

map： map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素，因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了map的效率。

unordered_map: unordered_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的

文章最后发布于: 2019-09-07 21:09:42

so easy（并查集）

so easy

so easy

代码实现

unordered_map

map与unordered_map的区别

相关阅读

栏目导航

推荐阅读

热门阅读