对于以下等价类，采用“加权合并规则”（也称“重量权衡合并规则”），进行并查运算，给出最后父节点索引序列。For the following equivalence class, please use “weighted union rule” and UNION/FIND algorithm to write down the final parent node index sequence. 4-0 6-2 8-4 9-4 3-5 9-5 5-2 1-2 7-1 注意：当合并大小相同的两棵树的时候，将第二棵树的根指向第一棵树的根；根节点的索引是它本身；数字之间用空格隔开。 Notice: When we join two trees with the same size, we let the root of the second tree point to the root of the first tree. The index of the root node is itself. Separate the numbers with only one spaces.
using namespace std; int p[15], Size[15]; void init(){ for (int i = 0; i < 10; i++) p[i] = i, Size[i] = 1; } int Find(int x){ return x == p[x] ? x : Find(p[x]); } void Union(int a, int b){ int pa = Find(a), pb = Find(b); if (pa != pb){ if (Size[pa] >= Size[pb]){ p[pb] = pa; Size[pa] += Size[pb]; } else{ p[pa] = pb; Size[pb] += Size[pa]; } } } int main(){#ifdef ONLINE_JUDGE#elsefreopen("in.txt", "r", stdin);#endif init(); for (int i = 0; i < 9; i++){ int a, b; scanf("%d%d", &a, &b); Union(a, b); } for (int i = 0; i < 10; i++){ printf("%d ", p[i]); } return 0; }
12345678910111213141516171819202122232425262728293031323334353637383940
