Weighted version of quick union

Weighted version of quick union

深刻了解代碼中數組sz[]所起的權重的作用

#include <iostream>
using namespace std;

const int N = 100;

int main()
{
	int i, j;
	int p, q;
	int id[N], sz[N];  // 數組sz[]表示子樹中節點的數量

	for (i=0; i<N; i++)
	{
		id[i] = i;
		sz[i] = 1;
	}

	while (cin>>p>>q)
	{
		// find the root of p
		for (i=p; i != id[i]; i=id[i])
		{
		}

		// find the root of q
		for (j=q; j != id[j]; j=id[j])
		{
		}

		if (i == j)
		{
			continue;
		}

		// weighted version of quick union
		if (sz[i] < sz[j])
		{
			id[i] = j;
			sz[j] += sz[i];
		}
		else
		{
			id[j] = i;
			sz[i] += sz[j];
		}

		cout<<p<<"  "<<q<<endl;
	}

	system("pause");
	return 0;
}
           

quick union測試用例圖解：

Tree representation of weighted quick union

weighted quick union(worst case)