Codeforces Round #541 (Div. 2) F、Asya And Kittens||并查集 F、Asya And Kittens 当时在比赛的时候没注意到这题，其实还是很好做的； 思维： 每次需要将一起玩的猫放在一个集合中就可以很简单的模拟过程； 懂并查集的同学也可以很轻松的实现集合的查找和合并； 不懂的同学向大家推荐一个大佬的博客； 那么接下的问题就是如何将集合中的

题目大意是说，输入 n n n，表示有 n n n个数 1 1 1~ n n n，接下来有 n − 1 n-1 n−1对关系，每行输入两个数 a a a和 b b b，表示将 a a a所在的集合与 b b b所在的集合合并，但是合并有前提条件， a a a所在的集合与 b b b所在的集合必须相邻（数组的第一个和最后一个不算相邻）。求这组序列最开始的排列情况，答案不唯一，输出一组答案即可 做

https://codeforces.com/problemset/problem/1131/F 思路: 对于每一个编号，我们将其连边都看作他的儿子，然后将儿子的状态最后都更新到他本身。 看成他的儿子就变成了树形结构。这里借用大佬的图 对于 1 3 1 2 4 5 4 6 1 4 G[1] = {3,2,4}，每个子树都保证顺序可行，那么合并起来的顺序也是可行的。   可以看到

有 n 只猫，原来分别在一个笼子里，但是相邻的猫想一起玩就将它们放在一个笼子里，但是现在它们凑成了一堆，问他们原来在几号笼子里  const int N=15*1e4+5;int n,m,t;int i,j,k;int fa[N];list<int> l[N];int Find(int x){return fa[x]==x? x: fa[x]=Find(fa[x]);}int ma

题目描述：   算法：并查集         使用两个并查集vl, vr分别记录当前集合的最左元素和最右元素，在合并时将记录最左元素的根节点接在左侧集合的根节点下，记录右侧的接在右侧根节点下即vr[ar] = br, vl[bl] = al，ar, br为两个集合的根节点。         在拼接过程中再记录拼接点的左右元素分别是谁，即r[ar] = bl, l[bl] = ar。