I was coding for 217A - Ice Skating but I got wrong answer on test 12, can anyone help me out with debugging this code?
Idea: bipartite graph (Union x and y for every point, xs are from 0 to 999 and ys are from 1000 to 1999) What I am doing is subtracting those components with size equal to one that from 2000. The remaining number is equal to the number of components.
#include <iostream>
#include <vector>
using namespace std;
class DSU {
public:
int size;
int components;
vector<int> component_size;
vector<int> id;
DSU(int size) {
this->size = size;
this->components = size;
this->component_size.resize(size, 1);
this->id.resize(size);
for(int i = 0; i < size; i++) {
id[i] = i;
}
}
int getSize() {
return this->size;
}
int Find(int a) {
int root = a;
while(root != id[root]) {
root = id[root];
}
while(a != root) {
id[a] = root;
a = id[a];
}
return root;
}
int Union(int a, int b) {
int root_a = Find(a);
int root_b = Find(b);
if(root_a == root_b) {
return root_a;
} else {
if (component_size[root_a] > component_size[root_b]) {
component_size[root_a] += component_size[id[root_b]];
components--;
return id[root_b] = root_a;
} else {
component_size[root_b] += component_size[id[root_a]];
components--;
return id[root_a] = root_b;
}
}
}
void Show() {
for(int i=0; i<size; i++) {
cout << i << ' ' << id[i] << endl;
}
cout << endl;
for(int i=0; i<size; i++) {
cout << i << ' ' << component_size[Find(i)] << endl;
}
}
};
void test();
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
t = 1;
// cin >> t;
while(t--) {
test();
cout << endl;
}
}
void test() {
int n;
cin >> n;
DSU dsu(2000);
for(int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
dsu.Union(x - 1, 1000 + y - 1);
}
int ans = 2000;
for(int i=0; i<2000; i++) {
dsu.Find(i);
if(dsu.component_size[i] == 1) {
ans--;
}
}
cout << ans - 1 << endl;
}
See this case
When the 3rd line is processed, there are 2 components {x=1,y=1} and {x=2,y=2}. then these will be connected,
component_size
will be 2 and 4, and your output will be 1.Thankyou for your great help. I
was wrong on computing the components.
I fixed my code with changing my last loop:
The main idea is executing Find function for every unchecked element for path compression.
Wow.. great catch .,.. this really helped me understand the topic better..!!