Skip to content

Commit a814bad

Browse files
rudi8848rudi8848
committed
disjoin set solved
1 parent 7521d95 commit a814bad

4 files changed

Lines changed: 179 additions & 14 deletions

File tree

‎2/auto_analysis.cpp‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
#include <iostream>
2+
#include <vector>
3+
4+
class DisjoinSet
5+
{
6+
public:
7+
DisjoinSet(unsigned numVariables) {
8+
_rank.resize(numVariables + 1);
9+
_parent.resize(numVariables + 1);
10+
for (int i = 1; i < numVariables + 1; ++i)
11+
makeSet(i);
12+
13+
}
14+
~DisjoinSet() {}
15+
16+
void join(unsigned i, unsigned j) {
17+
18+
unsigned i_id, j_id;
19+
20+
i_id = find(i);
21+
j_id = find(j);
22+
if (i_id == j_id)
23+
return;
24+
if (_rank[i_id] > _rank[j_id]) {
25+
_parent[j_id] = i_id;
26+
}
27+
else {
28+
_parent[i_id] = j_id;
29+
if (_rank[i_id] == _rank[j_id])
30+
_rank[j_id] += 1;
31+
}
32+
}
33+
34+
unsigned find(unsigned i) {
35+
while (i != _parent[i])
36+
i = _parent[i];
37+
return i;
38+
}
39+
private:
40+
void makeSet(unsigned i) {
41+
_parent[i] = i;
42+
_rank[i] = 0;
43+
}
44+
45+
std::vector<unsigned> _parent;
46+
std::vector<unsigned> _rank;
47+
};
48+
49+
int main(void)
50+
{
51+
unsigned numVariables, equal, notEqual;
52+
53+
std::cin >> numVariables >> equal >> notEqual;
54+
55+
if (!notEqual) {
56+
std::cout << "1" << std::endl;
57+
return 0;
58+
}
59+
60+
DisjoinSet set(numVariables);
61+
62+
for (int i = 0; i < equal; ++i){
63+
unsigned a, b;
64+
std::cin >> a >> b;
65+
set.join(a, b);
66+
}
67+
for (int i = 0; i < notEqual; ++i) {
68+
unsigned a, b;
69+
std::cin >> a >> b;
70+
if (set.find(a) == set.find(b)) {
71+
std::cout << "0" << std::endl;
72+
return 0;
73+
}
74+
}
75+
std::cout << "1" << std::endl;
76+
return 0;
77+
}

‎2/join_database.cpp‎

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
#include <iostream>
2+
#include <vector>
3+
4+
class Database
5+
{
6+
public:
7+
Database(unsigned numTables) {
8+
//std::cout << __PRETTY_FUNCTION__ << std::endl;
9+
_tables.resize(numTables + 1);
10+
_rank.resize(numTables + 1);
11+
_parent.resize(numTables + 1);
12+
_maxSize = 0;
13+
for (int i = 1; i < numTables + 1; ++i) {
14+
std::cin >> _tables[i];
15+
if (_tables[i] > _maxSize)
16+
_maxSize = _tables[i];
17+
makeSet(i);
18+
}
19+
}
20+
~Database(){}
21+
22+
void join(unsigned i, unsigned j) {
23+
//std::cout << __PRETTY_FUNCTION__ << std::endl;
24+
unsigned i_id, j_id;
25+
26+
i_id = find(i);
27+
j_id = find(j);
28+
if (i_id == j_id)
29+
return;
30+
if (_rank[i_id] > _rank[j_id]) {
31+
_parent[j_id] = i_id;
32+
_tables[i_id] += _tables[j_id];
33+
_tables[j_id] = 0;
34+
}
35+
else {
36+
_parent[i_id] = j_id;
37+
if (_rank[i_id] == _rank[j_id])
38+
_rank[j_id] += 1;
39+
_tables[j_id] += _tables[i_id];
40+
_tables[i_id] = 0;
41+
}
42+
unsigned max = std::max(_tables[j_id], _tables[i_id]);
43+
_maxSize = std::max(max, _maxSize);
44+
}
45+
46+
unsigned maxSize() { return _maxSize; }
47+
48+
void print() {
49+
for (int i = 1; i < _tables.size(); ++i) {
50+
std::cout << "tables [" << _tables[i] << "]\tparent ["
51+
<< _parent[i] << "]\trank [" << _rank[i] << "]"<< std::endl;
52+
}
53+
std::cout << "----------------------------" << std::endl;
54+
}
55+
private:
56+
void makeSet(unsigned i) {
57+
//std::cout << __PRETTY_FUNCTION__ << std::endl;
58+
_parent[i] = i;
59+
_rank[i] = 0;
60+
}
61+
62+
unsigned find(unsigned i) {
63+
//std::cout << __PRETTY_FUNCTION__ << std::endl;
64+
while (i != _parent[i])
65+
i = _parent[i];
66+
return i;
67+
}
68+
unsigned _maxSize;
69+
std::vector<unsigned> _tables;
70+
std::vector<unsigned> _parent;
71+
std::vector<unsigned> _rank;
72+
};
73+
74+
int main(void) {
75+
76+
int numTables, numRequests;
77+
78+
std::cin >> numTables >> numRequests;
79+
80+
Database database(numTables);
81+
//database.print();
82+
for (int i = 0; i < numRequests; ++i) {
83+
int dest, src;
84+
std::cin >> dest >> src;
85+
database.join(dest, src);
86+
//database.print();
87+
std::cout << database.maxSize() << std::endl;
88+
}
89+
90+
return 0;
91+
}

‎2/min_heap.cpp‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -103,11 +103,11 @@ int main(void)
103103
std::cin >> v[i];
104104

105105
MinHeap heap(v);
106-
106+
/*
107107
for (int i = 0; i < n; ++i)
108108
std::cout << heap.heap()[i] << " ";
109109
std::cout << std::endl;
110-
110+
*/
111111
std::cout << heap.log().size() << std::endl;
112112
if (heap.log().size()) {
113113
for (int i = 0; i < heap.log().size(); ++i) {

2/proc.cpp renamed to 2/parallel_processing.cpp

Lines changed: 9 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -15,15 +15,14 @@ class MinHeap
1515
++i;
1616
}
1717
_size = processors;
18-
_maxSize = _heap.capacity();
1918
BuildHeap();
2019

2120
i = 0;
2221
while (i < tasks)
2322
{
2423
int task;
2524
std::cin >> task;
26-
ChangePriority(0, task);
25+
ChangePriority(task);
2726
++i;
2827
}
2928
}
@@ -42,7 +41,6 @@ class MinHeap
4241
int LeftChild(int i) { return 2 * i + 1; }
4342
int RightChild(int i) { return 2 * i + 2; }
4443
int size() { return _size; }
45-
int maxSize() { return _maxSize; }
4644

4745
void SiftDown(int i) {
4846
int minIndex = i;
@@ -62,19 +60,18 @@ class MinHeap
6260
}
6361
}
6462

65-
void ChangePriority(int i, unsigned long time) {
66-
_log.push_back(std::make_pair(_heap[i].second, _heap[i].first));
67-
_heap[i].first += time;
68-
SiftDown(i);
63+
void ChangePriority(unsigned long time) {
64+
_log.push_back(std::make_pair(_heap[0].second, _heap[0].first));
65+
_heap[0].first += time;
66+
SiftDown(0);
6967
}
70-
std::vector<std::pair<long, int>> const & heap() { return _heap; }
68+
std::vector<T> const & heap() { return _heap; }
7169
std::vector<std::pair<int, unsigned long>> const & log() { return _log;}
7270

7371
private:
74-
std::vector<T> _heap;
75-
std::vector<std::pair<int, unsigned long>> _log;
76-
int _size;
77-
int _maxSize;
72+
std::vector<T> _heap;
73+
std::vector<std::pair<int, unsigned long>> _log;
74+
int _size;
7875
};
7976

8077
int main(void)

0 commit comments

Comments
 (0)