Codeforces Round #541 (Div. 2) F、Asya And Kittens||并查集

Codeforces Round #541 (Div. 2) F、Asya And Kittens||并查集

F、Asya And Kittens
当时在比赛的时候没注意到这题，其实还是很好做的；
思维：
每次需要将一起玩的猫放在一个集合中就可以很简单的模拟过程；
懂并查集的同学也可以很轻松的实现集合的查找和合并；
不懂的同学向大家推荐一个大佬的博客；
那么接下的问题就是如何将集合中的数输出了，我们可以维护一个数组（代码中使用link），将每个数的下一个数记录下来；
同时为了配合记录需要维护集合第一个元素和最后一个元素（第一个元素即为并查集集合标号，最后一个元素也可以用一个数组back维护）；
那么大功告成，上代码：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int f[160000], back[160000], link[160000];
int find(int x)
{while (x != f[x])x = f[x] = f[f[x]];return x;
}
int main()
{int n, u, v, eu, ev; cin >> n;for (int i = 1; i <= n; i++)f[i] = i, back[i] = i;for (int i = 1; i < n; i++){cin >> u >> v;eu = find(u); ev = find(v);f[ev] = eu;link[back[eu]] = ev;//记录该元素的下一个元素back[eu] = back[ev];//维护集合的最后一个元素}for (int i = 1; i <= n; i++){if (f[i] == i)//如果父节点为本身，那么就是集合标志{int next = i;cout << next << ' ';while (link[next])//如果下一个元素为空，结束{next = link[next];cout << next << ' ';}}}
}