Union-Find Disjoint Sets Practice questions.

Practice Questions

Here are the questions you can do to practice Union-Find Disjoint Sets.

1. UVa 00793 - Network Connections *
2. UVa 01197 - The Suspects
3. UVa 10158 - War
4. UVa 10227 - Forests
5. UVa 10507 - Waking up brain 
6. UVa 10583 - Ubiquitous Religions
7. UVa 10608 - Friends
8. UVa 10685 - Nature
9. UVa 11503 - Virtual Friends
10. UVa 11690 - Money Matters



Here are my solutions and hints to some of these problems:

Hints and solutions

We are using the implementation we discussed previously. Here I am sharing it again:

class UnionFind{
private: vector<int> p, rank;
public:
UnionFind(int N){//N is the number of elements
rank.assign(N, 0);//////create n nodes assign 0 to each
p.assign(N,0);
for(int i=0;i<N;i++)
p[i]=i;
}
int findSet(int i){
return (p[i]==i)?i: (p[i]=findSet(p[i])); //also doing the path compression simultaneously
}
bool isSameSet(int i, int j){
return findSet(i)==findSet(j);
}
void unionSet(int i, int j){
if(!isSameSet(i,j)){
int x=findSet(i), y=findSet(j);
if(rank[x]>rank[y])
p[y]=x;
else{
p[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
}
int numDisjointSets(){
set<int> set;
for(int i=0;i<p.size();i++){
int a=p[i];
set.insert(findSet(a));
}
return set.size();
}
int sizeOfSet(int i){
int t = findSet(i);
int count=0;
for(int i=0;i<p.size();i++){
int a = p[i];
if(t==findSet(a)){
count++;
}
}
return count;
}
};


All the problems in this category are very similar. You are given what points are connected and are either asked if two points are connected or similar such questions.

Uva 00793. Network Connections

int main(int argc, char const *argv[]) {
int t;
scanf("%d", &t);
int temp=1;
while (t--) {
int numberofComp;
scanf("\n%d\n", &numberofComp);
UnionFind uf(numberofComp);
char ch;
int a, b;
int successfulanswers=0;
int failure=0;
string s;
while (1) {
if(!getline(cin, s)||s.empty())
break;
sscanf(s.c_str(), "%c %d %d", &ch, &a, &b);
if(ch=='c')
uf.unionSet(a-1, b-1);
if(ch=='q'){
if(uf.isSameSet(a-1, b-1))
successfulanswers++;
else
failure++;
}
}
if(temp!=1)
cout<<endl;
cout<<successfulanswers<<','<<failure<<endl;
temp++;
}
return 0;
}

Uva 10608 Friends

int main(int argc, char const *argv[]) {
int T;
scanf("%d", &T);
while (T--) {
int N, M;
scanf("%d %d", &N, &M);
UnionFind uf(N);
while (M--) {
int a, b;
scanf("%d %d", &a, &b);
uf.unionSet(a-1, b-1);
}
std::vector<int> arr;
arr.assign(N, 0);
for (size_t i = 0; i < N; i++) {
arr[uf.findSet(i)]++;
}
sort(arr.begin(), arr.end());
cout<<arr[N-1]<<endl;
}
return 0;
}

Uva 0583 Ubiquitous Religions


int main(int argc, char const *argv[]) {
int k=1;
while(true){
int n, m;
scanf("%d %d", &n, &m);
if(n==0&&m==0)
break;
UnionFind uf(n);
while(m--){
int a, b;
scanf("%d %d", &a, &b);
uf.unionSet(a-1, b-1);
}
printf("Case %d: %d\n", k++, uf.numDisjointSets());
}
return 0;
}

Installing albert on ubuntu 19.04

Installing Albert on Ubuntu 19.04... Albert is not still released for ubuntu 19.04. But still, you can install it using the following ...