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 is the link to the set of questions: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=636

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;
	}