-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathDSU.cpp
More file actions
105 lines (95 loc) · 2.22 KB
/
DSU.cpp
File metadata and controls
105 lines (95 loc) · 2.22 KB
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
//
// Created by teitoku on 2022-03-20.
//
#include <Eigen/Dense>
#include <map>
#include <thread>
#include "DSU.h"
#include <chrono>
unsigned long long DSU::find_root(unsigned long long id) {
if(pre.find(id) == pre.end())
pre[id]=id;
unsigned long long r = id;
while (pre[r] != r) {
r = pre[r];
}
while (pre[id] != r) {
unsigned long long y = pre[id];
pre[id] = r;
id = y;
}
return r;
}
void DSU::join(unsigned long long x, unsigned long long y) {
if (find_root(x) != find_root(y)) {
pre[find_root(x)] = find_root(y);
}
return;
}
std::unordered_map<unsigned long long,int> DSU::encode(int &encode_cnt){
std::unordered_map<unsigned long long,int> ret;
encode_cnt = 0;
for(auto i : pre){
if(find_root(i.first) == i.first){
ret[i.first]=encode_cnt++;
}
}
for(auto i : pre){
if(find_root(i.first) != i.first){
ret[i.first]=ret[find_root(i.first)];
}
}
return ret;
}
void DSUMultiThread::inner_join(int x,int y) {
if (find_root(x) != find_root(y)) {
pre[find_root(x)] = find_root(y);
}
return;
}
int DSUMultiThread::find_root(int id) {
int r = id;
while (pre[r] != r) {
r = pre[r];
}
while (pre[id] != r) {
int y = pre[id];
pre[id] = r;
id = y;
}
return r;
}
DSUMultiThread::DSUMultiThread(int x){
pre.resize(x+10);
for(int i=0;i<x+10;i++){
pre[i] = i;
}
}
void DSUMultiThread::run(){
join_thread = std::make_shared<std::thread>([&](){
while(1){
std::unique_lock<std::mutex> lck(mu2);
cv.wait(lck, [&]() {
return !q.empty();
});
std::unique_lock<std::mutex> lck2(mu1);
std::pair<int,int> p = q.front();
q.pop();
if(p.first<0 && p.second < 0){
break;
}
inner_join(p.first,p.second);
}
return ;
});
}
void DSUMultiThread::join(int x, int y) {
std::unique_lock<std::mutex> lck2(mu1);
q.push({x,y});
cv.notify_one();
}
void DSUMultiThread::stop() {
std::unique_lock<std::mutex> lck2(mu1);
q.push({-1,-1});
cv.notify_one();
}