备赛蓝桥杯和icpc的习题：
一道并查集的题目
> #include<iostream>
> #include<vector>
> #include<algorithm>
> #include<math.h>
> #include<string>
> #include<string.h>
> #include<iomanip>
> #include<map>
> #include<queue>
> using namespace std;
> typedef long long ll;
> int n;//n个整数
> ll mp[100010] = { 0 };//存储初始数据
> ll s[100010] = { 0 };//存储i对应的终点：s[i]
> void init()//初始化
> {
> for (ll i = 1; i <= 100000; i++)s[i] = i;
> }
> ll merge_(ll i)//合并，同时路径压缩
> {
> if (s[i] != i)s[i]=merge_(s[i]);
> return s[i];
> }
> int main()
> {
> cin >> n;
> for (int i = 1; i <= n; i++)cin >> mp[i];
> init();
>
> for (int i = 1; i <= n; i++)
> {
> ll th = mp[i];//记录前驱，修改的节点，因为不记录的话会被下一行的mp[i]更新
> mp[i] = s[merge_(mp[i])];//所有都要修改，沿途之处不一定是终点，只有遍历到i=s[i]时才正确
> s[merge_(mp[i])]++;//增加1，使得下一个重复的点可以增加
> merge_(th);//合并，路径压缩
> }
> for (int i = 1; i <= n; i++)cout << mp[i] << ' ';
> return 0;
> }
debug了10几分钟，难绷。
