合作网络（Corporative Network ）并查集+路径压缩

 1 #include <iostream> 2 #include <algorithm> 3 #include <string> 4 using namespace std; 5 ?6 const int maxn = 20000 + 5; 7 int fa[maxn]; 8 int d[maxn]; 9 10 int Find(int x){11 ????if (fa[x] != x){12 ????????int root = Find(fa[x]);13 ????????d[x] += d[fa[x]]; ???//路径压缩维护d[i]14 ????????return fa[x] = root;15 ????}16 ????else17 ????????return x;18 }19 20 int main(){21 ????/*22 ????freopen("in.txt", "r", stdin);23 ????freopen("out.txt", "w", stdout);24 ????*/25 ????int t;26 ????cin >> t;27 ????while (t--){28 ????????int n;29 ????????cin >> n;30 ????????31 ????????//init32 ????????for (int i = 1; i <= n; i++){33 ????????????fa[i] = i;34 ????????????d[i] = 0;35 ????????}36 37 ????????string s;38 ????????while (cin >> s){39 ????????????if (s[0] == ‘O‘)40 ????????????????break;41 ????????????if (s[0] == ‘I‘){42 ????????????????int a, b;43 ????????????????cin >> a >> b;44 ????????????????fa[a] = b;45 ????????????????d[a] = abs(a - b) % 1000;46 ????????????}47 ????????????else{48 ????????????????int c;49 ????????????????cin >> c;50 ????????????????Find(c);51 ????????????????cout << d[c] << endl;52 ????????????}53 ????????}54 ????}55 ????/*56 ????fclose(stdin);57 ????fclose(stdout);58 ????*/59 ????return 0;60 }