题号：P1196
参见题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1196
结合源代码阅读才好……
推荐题解作者：作者: 超神火星人 更新时间: 2017-04-29 09:14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include<iostream> #include<algorithm> #include<string> #include<cstdlib> #include<cstring> #include<utility> int father[30005],size[30005],front[30005]; using namespace std; int sfind(int node){ if (father[node] == -1)return node; int fn = sfind(father[node]); front[node] += front[father[node]]; return father[node]=fn; } int main(){ for (int i = 1; i <= 30000; i++){ father[i] = -1; size[i] = 1; front[i] = 0; } ios::sync_with_stdio(false); int n; cin >> n; while (n--){ char c; int rf1, rf2; cin >> c >> rf1 >> rf2; int fa1 = sfind(rf1); int fa2 = sfind(rf2); switch (c){ case 'M': front[fa1] += size[fa2]; father[fa1] = fa2; size[fa2] += size[fa1]; size[fa1] = 0; break; case 'C': if (fa1 != fa2)cout << "-1" << endl; else cout << abs(front[rf1] - front[rf2])-1 << endl; break; } } } |
20180815更新：
重做了这道题，还是看的这个人的题解。。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include<iostream> using namespace std; int t; int father[30005],front[30005],num[30005]; int _find(int node){ if(father[node]==0)return node; int fn=_find(father[node]); front[node]+=front[father[node]]; return father[node]=fn; } int main(){ ios::sync_with_stdio(false); for(int i=1;i<=30000;i++)num[i]=1; cin>>t; while(t--){ char op; int x,y; cin>>op>>x>>y; int fx=_find(x),fy=_find(y); if(op=='M'){ front[fx]+=num[fy]; father[fx]=fy; num[fy]+=num[fx]; num[fx]=0; }else{ if(fx!=fy)cout<<-1<<endl; else cout<<abs(front[x]-front[y])-1<<endl; } } } |
发现越到后面就越感觉是在抄题解怎么办，想也想不出来。