Algorithms-4th-C-Coding/WeightUF.cpp at master · superlich7/Algorithms-4th-C-Coding · GitHub

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
using namespace std;

class WeightUF
{
	private:
		int *id;
		int *sz;//child num of each id
		int num;//total id num

	public:
		WeightUF(int n);
		~WeightUF();
		int root(int p);
		bool Connected(int p, int q);
		void Union(int p, int q);
};

WeightUF::WeightUF(int n)
{
	id = new int[n];
	sz = new int[n];
	for(int i=0;i<n;i++)
	{
		id[i] = i;
		sz[i] = 0;
	}
	num = n;

	cout << "New UF obj with elements " << num << endl;
}

WeightUF::~WeightUF()
{
	delete id;
	delete sz;
	num = 0;
}

int WeightUF::root(int p)
{
	while(id[p] != p)
	{
		id[p] = id[id[p]];
		p = id[p];
	}

	return p;
}

bool WeightUF::Connected(int p, int q)
{
	if(root(p) == root(q))
	{
		cout << p << " and " << q << " are connected !" << endl;
		return 1;
	}
	else
	{
		cout << p << " and " << q << " are NOT connected !" << endl;
	    return 0;
	}
}

void WeightUF::Union(int p, int q)
{
	int proot = root(p);
	int qroot = root(q);

	if(proot == qroot) return;
	if(sz[proot] < sz[qroot])
	{
		id[proot] = qroot;
		sz[qroot] += sz[proot];
	}
	else
	{
		id[qroot] = proot;
		sz[proot] += sz[qroot];
	}

	cout << p << " and " << q << " union !" << endl;

	return ;
}

int main()
{
	WeightUF oWeightUF(10);

	oWeightUF.Union(0,5);
	oWeightUF.Union(6,5);
	oWeightUF.Union(2,1);
	oWeightUF.Union(7,1);
	oWeightUF.Union(3,4);
	oWeightUF.Union(9,4);
	oWeightUF.Union(8,3);

	oWeightUF.Connected(0,6);
	oWeightUF.Connected(7,6);

	return 0;
}