-
Notifications
You must be signed in to change notification settings - Fork 8
/
disjoint_set_using_linked_list.c
145 lines (117 loc) · 2.81 KB
/
disjoint_set_using_linked_list.c
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/*
* Disjoint set using linked list
* Implements MAKE_SET, UNION and FIND_SET algorithms
*
* Test case directly copied from practice 21.2-2, CLRS 2nd
*/
#include <stdio.h>
#include <stdlib.h>
#define SET_CNT (16 + 1) /* Number of initial sets */
typedef int ELE_TYPE; /* Hold data type */
typedef struct _NODE NODE;
typedef struct _SET SET;
struct _NODE {
ELE_TYPE ele;
NODE *next;
NODE *rep;
SET *set; /* Which set the node belongs to */
};
struct _SET {
NODE *head;
NODE *tail;
int size;
};
NODE node_array[SET_CNT];
SET set_array[SET_CNT];
void make_set(ELE_TYPE ele)
{
SET *set;
NODE *node;
if (ele < 1 || ele > SET_CNT) {
return;
}
set = &set_array[ele];
node = &node_array[ele];
set->head = set->tail = node;
set->size = 1;
node->ele = ele;
node->next = NULL;
node->rep = node;
node->set = set;
return;
}
void union_set(ELE_TYPE left_ele, ELE_TYPE right_ele)
{
NODE *left_node;
NODE *right_node;
NODE *node;
SET *left;
SET *right;
if (left_ele < 1 || left_ele > SET_CNT
|| right_ele < 1 || right_ele > SET_CNT) {
return;
}
left_node = &node_array[left_ele];
right_node = &node_array[right_ele];
left = left_node->set;
right = right_node->set;
/*
* The weighted-union rule is also following that of practice 21.2-2,
* CLRS 2nd: if the sets have the same size, then UNION(xi, xj) appends
* xj's list onto xi's list
*/
if (left->size < right->size) {
right->tail->next = left->head;
right->tail = left->tail;
node = left->head;
while (node != NULL) {
node->rep = right->head;
node->set = right;
node = node->next;
}
right->size += left->size;
left->head = left->tail = NULL;
left->size = 0;
}
else {
left->tail->next = right->head;
left->tail = right->tail;
node = right->head;
while (node != NULL) {
node->rep = left->head;
node->set = left;
node = node->next;
}
left->size += right->size;
right->head = right->tail = NULL;
right->size = 0;
}
}
NODE* find_set(ELE_TYPE ele)
{
if (ele < 1 || ele > SET_CNT) {
return NULL;
}
return node_array[ele].rep;
}
int main()
{
int i;
ELE_TYPE ele;
for (i = 1; i <= SET_CNT; i++) {
ele = (ELE_TYPE)i;
make_set(ele);
}
for (i = 1; i <= SET_CNT - 1; i += 2) {
union_set(i, i + 1);
}
for (i = 1; i <= SET_CNT - 3; i += 4) {
union_set(i, i + 2);
}
union_set(1, 5);
union_set(11, 13);
union_set(1, 10);
printf("%d\n", find_set(2)->ele);
printf("%d\n", find_set(9)->ele);
return 0;
}