Union-Find Problem Sets
Contents
Union-find data structure is used extensively to solve problems associated with disjoint sets. Two sets are called disjoint sets if they don’t have any common elements. It supports the following operations:
- Find: finding a representative of the set
- Merge: merge two disjoint sets to form a single set
To optimize the find operation, always assign the representative as the node having the highest rank. This is similar to assigning the subtree with a lower height as a child under the subtree with a higher height, thus reducing the complexity. With union-by-rank and path compression, both operations run in amortized time, where is the inverse Ackermann function (grows so slowly it is for any practical ).
This is useful in solving problems involving relationships, especially the ones that can be described with undirected graphs. Detecting the presence of a cycle in an undirected graph is one such example. For detecing cycle in directed graph, topological sort is used.
This wiki contains a couple of well-defined problems solved via Union-Find data structure.
Graph Valid Tree (178):
Show solution
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
int find(vector<int> &parent, int index){
int root = index;
while(parent[root] != root){
root = parent[root];
}
return root;
}
void unionSet(vector<int> &parent,vector<int> &rank, int index1, int index2){
int root1 = find(parent, index1);
int root2 = find(parent, index2);
if (rank[root1] < rank[root2]){
parent[root1] = root2;
} else if(rank[root1] > rank[root2]){
parent[root2] = root1;
} else {
parent[root1] = root2;
rank[root2]++;
}
}
bool validTree(int n, vector<vector<int>> &edges) {
// write your code here
vector<int> parent(n), rank(n,0);
for(int i=0;i<n;i++){
parent[i] = i;
}
for(int i=0;i<edges.size();i++){
int node1=edges[i][0], node2=edges[i][1];
int root1 = find(parent, node1);
int root2 = find(parent, node2);
if(root1 == root2){
return false;
}
unionSet(parent, rank, node1, node2);
}
int rootNodes=0;
for(int i=0;i<parent.size();i++){
if(parent[i] == i){
rootNodes++;
}
}
if(rootNodes>1){
cout<<"false root:"<<rootNodes<<endl;
return false;
}
return true;
}
Number of Islands II (434):
Show solution
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
pair<int,int> findRoot(pair<int,int> node){
pair<int,int> root = node;
while(parentMap.find(root) != parentMap.end()){
root = parentMap[root];
}
return root;
}
void unionSets(pair<int,int> index1, pair<int,int> index2){
pair<int,int> root1 = findRoot(index1);
pair<int,int> root2 = findRoot(index2);
if(root1 == root2){
return;
}if(rankMap[root1] < rankMap[root2]){
parentMap[root1] = root2;
} else if(rankMap[root1] > rankMap[root2]){
parentMap[root2] = root1;
} else {
parentMap[root1] = root2;
rankMap[root2]++;
}
groups--;
}
vector<int> numIslands2(int n, int m, vector<Point> &operators) {
// write your code here
parentMap.clear();
rankMap.clear();
groups = 0;
set<pair<int,int>> visitedPairSet;
vector<int> groupArray;
for(int i=0;i<operators.size();i++){
pair<int,int> node = make_pair(operators[i].x, operators[i].y);
if(visitedPairSet.find(node) != visitedPairSet.end()){
groupArray.push_back(groups);
continue;
}
groups++;
if(visitedPairSet.find( make_pair(node.first-1,node.second) ) != visitedPairSet.end() ){
unionSets(node, make_pair(node.first-1,node.second) );
}
if(visitedPairSet.find( make_pair(node.first+1,node.second) ) != visitedPairSet.end() ){
unionSets(node, make_pair(node.first+1,node.second) );
}
if(visitedPairSet.find( make_pair(node.first,node.second-1) ) != visitedPairSet.end() ){
unionSets(node, make_pair(node.first,node.second-1) );
}
if(visitedPairSet.find( make_pair(node.first,node.second+1) ) != visitedPairSet.end() ){
unionSets(node, make_pair(node.first,node.second+1) );
}
visitedPairSet.insert(node);
groupArray.push_back(groups);
}
return groupArray;
}
private:
map<pair<int,int>, pair<int,int>> parentMap;
map<pair<int,int>, int> rankMap;
int groups;
Accounts Merge (1070):
Show solution
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
int findRoot(vector<int> &parentArray, int index){
int root = index;
while(parentArray[root] != root){
root = parentArray[root];
}
return root;
}
void unionSets(vector<int> &parentArray, vector<int> &rankArray, int index1, int index2){
int root1 = findRoot(parentArray, index1);
int root2 = findRoot(parentArray, index2);
if(root1 == root2){
return;
}
// cout<<"merge2: "<<index1<<","<<index2<<":"<<root1<<","<<root2<<endl;
if(rankArray[root1] > rankArray[root2]){
parentArray[root2] = root1;
} else if(rankArray[root2] > rankArray[root1]){
parentArray[root1] = root2;
} else {
parentArray[root2] = root1;
rankArray[root1]++;
}
}
vector<vector<string>> accountsMerge(vector<vector<string>> &accounts) {
// write your code here
vector<int> parentArray(accounts.size()), rankArray(accounts.size(),0);
for(int i=0;i<parentArray.size();i++){
parentArray[i] = i;
}
map<string, int> emailMapper;
for(int i=0;i<accounts.size();i++){
string accOwner = accounts[i][0];
for(int j=1;j<accounts[i].size();j++){
if(emailMapper.find(accounts[i][j]) != emailMapper.end()){
// cout<<"merging "<<i<<" with "<<emailMapper[accounts[i][j]]<<" for "<<accounts[i][j]<<endl;
unionSets(parentArray, rankArray, i, emailMapper[accounts[i][j]]);
} else {
emailMapper[accounts[i][j]] = i;
}
}
}
map<int, set<string>> mergedMapper;
for(int i=0;i<accounts.size();i++){
int root = findRoot(parentArray, i);
// cout<<"root of index "<<i<<" : "<<root<<endl;
for(int j=1;j<accounts[i].size();j++){
mergedMapper[root].insert(accounts[i][j]);
}
}
vector<vector<string>> result;
for(auto const &pr : mergedMapper){
vector<string> arr;
arr.push_back(accounts[pr.first][0]);
for(const string &str : pr.second){
arr.push_back(str);
}
result.push_back(arr);
}
return result;
}
Maximum Connected Area (261):
Show solution
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
pair<int,int> findRoot(pair<int,int> index){
pair<int,int> root = index;
while(parentMap.find(root) != parentMap.end()){
root = parentMap[root];
}
return root;
}
void mergeSet(pair<int,int> index1, pair<int,int> index2){
// cout<<"merging indexs1 : ("<<index1.first<<","<<index1.second<<") ("<<index2.first<<","<<index2.second<<")"<<endl;
pair<int,int> root1=findRoot(index1), root2=findRoot(index2);
int rank1=rankMap[root1], rank2=rankMap[root2];
if(root1==root2){
return;
}
// cout<<"merging indexs2 : ("<<root1.first<<","<<root1.second<<") ("<<root2.first<<","<<root2.second<<")"<<endl;
if(rank1 > rank2){
parentMap[root2] = root1;
groupSizeMap[root1] += groupSizeMap[root2];
} else if(rank1 < rank2){
parentMap[root1] = root2;
groupSizeMap[root2] += groupSizeMap[root1];
} else {
parentMap[root2] = root1;
groupSizeMap[root1] += groupSizeMap[root2];
rankMap[root1]++;
}
}
bool isValid(vector<vector<int>> &grid, int i,int j){
if(i<0 || i>=grid.size()){
return false;
}
if(j<0 || j>=grid[i].size()){
return false;
}
if(grid[i][j] != 1){
return false;
}
return true;
}
int maxArea(vector<vector<int>> &matrix) {
// write your code here.
parentMap.clear();
rankMap.clear();
groupSizeMap.clear();
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[i].size();j++){
if(matrix[i][j] == 1){
groupSizeMap[make_pair(i,j)] = 1;
}
}
}
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[i].size();j++){
if(matrix[i][j] != 1){
continue;
}
pair<int,int> node = make_pair(i,j);
// cout<<"checking for node: ("<<i<<","<<j<<")"<<endl;
if(isValid(matrix, node.first-1, node.second)){
mergeSet(node, make_pair(node.first-1, node.second));
}
if(isValid(matrix, node.first+1, node.second)){
mergeSet(node, make_pair(node.first+1, node.second));
}
if(isValid(matrix, node.first, node.second-1)){
mergeSet(node, make_pair(node.first, node.second-1));
}
if(isValid(matrix, node.first, node.second+1)){
mergeSet(node, make_pair(node.first, node.second+1));
}
}
}
int maxArea = 0;
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[i].size();j++){
// cout<<"calc current area with index:"<<i<<","<<j<<": "<<endl;
int area = 1;
if(matrix[i][j] == 1){
pair<int,int> root = findRoot(make_pair(i,j));
area = groupSizeMap[root];
} else {
set<pair<int,int>> visitedRootSet;
if(isValid(matrix, i-1, j)){
pair<int,int> root = findRoot(make_pair(i-1,j));
if(visitedRootSet.find(root) == visitedRootSet.end()){
visitedRootSet.insert(root);
area += groupSizeMap[root];
// cout<<"1:"<<area<<endl;
}
}
if(isValid(matrix, i+1, j)){
pair<int,int> root = findRoot(make_pair(i+1,j));
if(visitedRootSet.find(root) == visitedRootSet.end()){
visitedRootSet.insert(root);
area += groupSizeMap[root];
// cout<<"2:"<<area<<endl;
}
}
if(isValid(matrix, i, j-1)){
pair<int,int> root = findRoot(make_pair(i,j-1));
if(visitedRootSet.find(root) == visitedRootSet.end()){
visitedRootSet.insert(root);
area += groupSizeMap[root];
// cout<<"3:"<<area<<endl;
}
}
if(isValid(matrix, i, j+1)){
pair<int,int> root = findRoot(make_pair(i,j+1));
if(visitedRootSet.find(root) == visitedRootSet.end()){
visitedRootSet.insert(root);
area += groupSizeMap[root];
// cout<<"4:"<<area<<endl;
}
}
}
// cout<<"current area with index:"<<i<<","<<j<<": "<<area<<endl;
maxArea = max(maxArea, area);
}
}
return maxArea;
}
private:
map<pair<int,int>, pair<int,int>> parentMap;
map<pair<int,int>, int> rankMap;
map<pair<int,int>, int> groupSizeMap;
Making A Large Island (1391):
Show solution
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
pair<int,int> findRoot(pair<int,int> index){
pair<int,int> root = index;
while(parentMap.find(root) != parentMap.end()){
root = parentMap[root];
}
return root;
}
void mergeSet(pair<int,int> index1, pair<int,int> index2){
// cout<<"merging index1: ("<<index1.first<<","<<index1.second<<") ("<<index2.first<<","<<index2.second<<")"<<endl;
pair<int,int> root1=findRoot(index1), root2=findRoot(index2);
int rank1=rankMap[root1], rank2=rankMap[root2];
if(root1==root2){
return;
}
// cout<<"merging index2: ("<<root1.first<<","<<root1.second<<") ("<<root2.first<<","<<root2.second<<")"<<endl;
if(rank1 > rank2){
parentMap[root2] = root1;
groupSizeMap[root1] += groupSizeMap[root2];
} else if(rank1 < rank2){
parentMap[root1] = root2;
groupSizeMap[root2] += groupSizeMap[root1];
} else {
parentMap[root2] = root1;
groupSizeMap[root1] += groupSizeMap[root2];
rankMap[root1]++;
}
}
bool isValid(vector<vector<int>> &grid, int i, int j){
if(i<0 || i>=grid.size()){
return false;
}
if(j<0 || j>=grid[i].size()){
return false;
}
if(grid[i][j] != 1){
return false;
}
return true;
}
int largestIsland(vector<vector<int>> &grid) {
//
parentMap.clear();
rankMap.clear();
groupSizeMap.clear();
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
groupSizeMap[make_pair(i,j)] = grid[i][j];
}
}
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
if(grid[i][j] != 1){
continue;
}
pair<int,int> node = make_pair(i,j);
if(isValid(grid, node.first-1, node.second)){
mergeSet(node, make_pair(node.first-1,node.second));
}
if(isValid(grid, node.first+1, node.second)){
mergeSet(node, make_pair(node.first+1,node.second));
}
if(isValid(grid, node.first, node.second-1)){
mergeSet(node, make_pair(node.first,node.second-1));
}
if(isValid(grid, node.first, node.second+1)){
mergeSet(node, make_pair(node.first,node.second+1));
}
}
}
int maxArea = 0;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[i].size();j++){
// cout<<"checking for index: "<<i<<","<<j<<endl;
int area = 1;
set<pair<int,int>> visitedSet;
if(grid[i][j]==1){
pair<int,int> root = findRoot(make_pair(i,j));
// cout<<"root index1 :"<<root.first<<","<<root.second<<endl;
area = groupSizeMap[root];
} else {
if(isValid(grid, i-1, j)){
pair<int,int> root = findRoot(make_pair(i-1,j));
if(visitedSet.find(root) == visitedSet.end()){
visitedSet.insert(root);
area += groupSizeMap[root];
}
}
if(isValid(grid, i+1, j)){
pair<int,int> root = findRoot(make_pair(i+1,j));
if(visitedSet.find(root) == visitedSet.end()){
visitedSet.insert(root);
area += groupSizeMap[root];
}
}
if(isValid(grid, i, j-1)){
pair<int,int> root = findRoot(make_pair(i,j-1));
if(visitedSet.find(root) == visitedSet.end()){
visitedSet.insert(root);
area += groupSizeMap[root];
}
}
if(isValid(grid, i, j+1)){
pair<int,int> root = findRoot(make_pair(i,j+1));
if(visitedSet.find(root) == visitedSet.end()){
visitedSet.insert(root);
area += groupSizeMap[root];
}
}
}
maxArea = max(maxArea, area);
}
}
return maxArea;
}
private:
map<pair<int,int>, pair<int,int>> parentMap;
map<pair<int,int>, int> rankMap, groupSizeMap;
Minimum Number of Visited Lattices in a Matrix (3709):
Show solution
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
bool isValid(vector<vector<int>> &grid, int i, int j){
if(i<0 || i>=grid.size()){
return false;
}
if(j<0 || j>=grid[i].size()){
return false;
}
return true;
}
int minimumVisitedLattices(vector<vector<int>> &grid) {
// --- write your code here ---
list<pair<pair<int,int>, int>> que;
set<pair<int,int>> visitedNodeSet;
que.push_back( make_pair( make_pair(0,0), 1));
visitedNodeSet.insert(make_pair(0,0));
while(que.size()!=0){
pair<pair<int,int>, int> node = que.front();
que.pop_front();
// cout<<"exploring node: "<<node.first.first<<","<<node.first.second<<" : "<<node.second<<endl;
if(node.first.first==grid.size()-1 && node.first.second==grid[grid.size()-1].size()-1){
return node.second;
}
for(int i=1;i<=grid[node.first.first][node.first.second];i++){
if(isValid(grid, node.first.first, node.first.second+i)){
if(visitedNodeSet.find(make_pair(node.first.first,node.first.second+i)) == visitedNodeSet.end()){
que.push_back( make_pair(make_pair(node.first.first,node.first.second+i), node.second+1) );
visitedNodeSet.insert(make_pair(node.first.first,node.first.second+i));
// cout<<"inserting node:"<<node.first.first<<","<<node.first.second+i<<endl;
}
}
if(isValid(grid, node.first.first+i, node.first.second)){
if(visitedNodeSet.find(make_pair(node.first.first+i,node.first.second)) == visitedNodeSet.end()){
que.push_back( make_pair(make_pair(node.first.first+i,node.first.second), node.second+1) );
visitedNodeSet.insert(make_pair(node.first.first+i,node.first.second));
// cout<<"inserting node:"<<node.first.first+i<<","<<node.first.second<<endl;
}
}
}
}
return -1;
}
The Minimum String After Swapping (3604):
Show solution
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
int findRoot(int index){
int root = index;
while(parentArray[root] != -1){
root = parentArray[root];
}
return root;
}
void mergeSet(int index1,int index2){
int root1=findRoot(index1), root2=findRoot(index2);
int rank1=rankArray[root1], rank2=rankArray[root2];
if(root1 == root2){
return;
}
if(rank1 > rank2){
parentArray[root2] = root1;
} else if(rank1 < rank2){
parentArray[root1] = root2;
} else {
parentArray[root2] = root1;
rankArray[root1]++;
}
}
string minStringAfterSwap(string &s, vector<vector<int>> &pairs) {
// // write your code here
parentArray.resize(s.size(), -1);
rankArray.resize(s.size(), 0);
for(int i=0;i<pairs.size();i++){
mergeSet(pairs[i][0], pairs[i][1]);
}
map<int, vector<char>> posMapper;
for(int i=0;i<s.size();i++){
int root = findRoot(i);
posMapper[root].push_back(s.at(i));
}
for(auto &pr : posMapper){
sort(pr.second.begin(), pr.second.end());
}
// for(auto const &pr: posMapper){
// cout<<"pr:"<<pr.first<<endl;
// for(int i=0;i<pr.second.size();i++){
// cout<<pr.second[i]<<",";
// }
// cout<<endl;
// }
map<int,int> posMapperIndexVisited;
for(auto const &pr: posMapper){
posMapperIndexVisited[pr.first] = -1;
}
string result = s;
for(int i=0;i<s.size();i++){
int root = findRoot(i);
posMapperIndexVisited[root]++;
result.at(i) = posMapper[root][posMapperIndexVisited[root]];
}
return result;
}
private:
vector<int> parentArray,rankArray;
Minimize Malware Spread (1718):
Show solution
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
int findRoot(int index){
int root = index;
while(parentArray[root] != -1){
root = parentArray[root];
}
return root;
}
void mergeSet(int index1, int index2){
// cout<<"merging "<<index1<<","<<index2<<endl;
int root1=findRoot(index1), root2=findRoot(index2);
int rank1=rankArray[root1], rank2=rankArray[root2];
if(root1 == root2){
return;
}
// cout<<"merging roots "<<root1<<","<<root2<<endl;
if(rank1 > rank2){
parentArray[root2] = root1;
groupSize[root1] += groupSize[root2];
} else if(rank1 < rank2){
parentArray[root1] = root2;
groupSize[root2] += groupSize[root1];
} else {
parentArray[root2] = root1;
groupSize[root1] += groupSize[root2];
rankArray[root1]++;
}
// cout<<"merged roots "<<root1<<","<<root2<<endl;
}
int minMalwareSpread(vector<vector<int>> &graph, vector<int> &initial) {
// write your code here
parentArray.resize(graph.size(), -1);
rankArray.resize(graph.size(), 0);
groupSize.resize(graph.size(), 1);
for(int i=0;i<graph.size();i++){
for(int j=0;j<graph[i].size();j++){
if(graph[i][j] == 1){
// cout<<"going to merge: "<<i<<","<<j<<endl;
mergeSet(i,j);
}
}
}
sort(initial.begin(),initial.end());
map<int,int> rootNodes;
for(int i=0;i<initial.size();i++){
int root = findRoot(initial[i]);
rootNodes[root]++;
}
int maxConnectedIndex=0, maxConnectedArea=0;
for(int i=0;i<initial.size();i++){
int root = findRoot(initial[i]);
if(rootNodes[root] > 1){
continue;
}
if(groupSize[root] > maxConnectedArea){
maxConnectedArea = groupSize[root];
maxConnectedIndex = i;
}
}
return initial[maxConnectedIndex];
}
private:
vector<int> parentArray, rankArray, groupSize;