Archive for the ‘Union find’ Category

UVA – 599 – The Forrest for the Trees   Leave a comment


Solved using union find
#include <stdio.h>
int set[26];
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
int main()
{
	int t,u;
	int cases = 0;
	int i,count[26];
	char letters[100],buffer[100];
	scanf("%d",&cases);
	getchar();
	while(cases--)
	{
		for(i=0;i<26;i++)
		{
			set[i]=i;
			count[i]=0;
		}
		while(gets(buffer)&&buffer[0]!='*')
			makeUnion(buffer[1]-'A',buffer[3]-'A',set);
		gets(letters);
		for(i=0;letters[i];i++)
			if(letters[i]!=',')
				count[getParent(letters[i]-'A',set)]++;
		t = u = 0;
		for(i=0;i<26;i++)
			if(count[i]>1)
				t++;
			else if(count[i]==1)
				u++;
		printf("There are %d tree(s) and %d acorn(s).\n",t,u);
	}
	return 0;
}
Advertisements

Posted August 22, 2011 by epicrado in Graph related, Union find

UVA – 11503 – Virtual Friends   Leave a comment


The trick is to cache the sum to avoid iteration over the disjoint set multiple times

#include <iostream>
#include <map>
#include <string>
#include <stdio.h>
using namespace std;
int getParent(int i, int *set) {
	if (i == set[i])
		return i;
	else
		return (set[i] = getParent(set[i], set));
}
int main() {
	int set[200005];
	int sum[200005];
	int cases;
	scanf("%d\n", &cases);
	while (cases--) {
		int n;
		scanf("%d\n", &n);
		int top = 1;
		for (int i = 1; i <= 2 * n; i++) {
			set[i] = i;
			sum[i] = 1;
		}
		map<string, int> hashmap;
		while (n-- > 0) {
			string s1, s2;
			cin >> s1 >> s2;
			int a, b;
			if (!hashmap[s1]) {
				a = top++;
				hashmap[s1] = a;
			} else
				a = hashmap[s1];
			if (!hashmap[s2]) {
				b = top++;
				hashmap[s2] = b;
			} else
				b = hashmap[s2];
			int p1 = getParent(a, set);
			int p2 = getParent(b, set);
			if (p1 != p2) {
				sum[p1] = sum[p1] + sum[p2];
				set[p2] = p1;
			}
			cout << sum[p1] << endl;
		}
	}
	return 0;
}

Posted August 22, 2011 by epicrado in Union find

UVA – 10685 – Nature   Leave a comment


import java.util.HashMap;
import java.util.Scanner;

public class Nature {
	static class DisjointSet {
		int[] set;

		DisjointSet(int n) {
			set = new int[n];
			int i = 0;
			while (i < n)
				set[i] = i++;
		}

		public int getParent(int i) {
			if (set[i] == i)
				return i;
			else
				return set[i] = getParent(set[i]);
		}

		public boolean isUnion(int a, int b) {
			return getParent(a) == getParent(b);
		}

		public void makeUnion(int a, int b) {
			set[getParent(a)] = getParent(b);
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int m = in.nextInt();
		int n = in.nextInt();
		while (n != 0 || m != 0) {
			HashMap<String, Integer> map = new HashMap<String, Integer>();
			for (int i = 0; i < m; i++)
				map.put(in.next(), i);
			DisjointSet set = new DisjointSet(m);
			int[] count = new int[m];
			while (n-- > 0)
				set.makeUnion(map.get(in.next()), map.get(in.next()));
			for (int i = 0; i < m; i++)
				count[set.getParent(i)]++;
			int max = 0;
			for (int i : count)
				max = Math.max(max, i);
			System.out.println(max);
			m = in.nextInt();
			n = in.nextInt();
		}
	}
}

Posted August 21, 2011 by epicrado in Union find

UVA – 793 – Network Connections   Leave a comment


#include <stdio.h>
int set[1000];
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
int isUnion(int a,int b,int* set)
{
	return getParent(a,set)==getParent(b,set);
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
int main()
{
	int c,c1,c2,computers;
	register int i,success,fail;
	char o,buffer[100];
	scanf("%d",&c);
	while(c--)
	{
		success=fail=0;
		scanf("%d",&computers);
		getchar();
		for(i=1;i<=computers;i++)set[i]=i;
		o=getchar();
		while(o!='\n'&&o!=EOF)
		{
			gets(buffer);
			sscanf(buffer,"%d %d",&c1,&c2);
			if(o=='q')
			{
				if(isUnion(c1,c2,set))
					success++;
				else
					fail++;
			}
			else
				makeUnion(c1,c2,set);
			o=getchar();
		}
		printf("%d,%d\n",success,fail);
		if(c)putchar('\n');
	}
	return 0;
}

Posted August 21, 2011 by epicrado in Union find

UVA – 10583 – Ubiquitous Religions   Leave a comment


#include <stdio.h>
#define max(a,b) (a>b)?a:b
int set[50005];
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
int isUnion(int a,int b,int* set)
{
	return getParent(a,set)==getParent(b,set);
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
int main()
{
	int c,i,k,n,m;
	scanf("%d %d",&n,&m);
	c = 1;
	while(n||m)
	{
		for(i=1;i<=n;i++)
			set[i]=i;
		while(m--)
		{
			scanf("%d %d",&i,&k);
			makeUnion(i,k,set);
		}
		m=0;
		for(k=1;k<=n;k++)
			m+=(getParent(k,set)==k);
		printf("Case %d: %d\n",c++,m);
		scanf("%d %d",&n,&m);
	}
	return 0;
}

Posted August 19, 2011 by epicrado in Union find

UVA – 10583 – Ubiquitous Religions   Leave a comment


#include <stdio.h>
#define max(a,b) (a>b)?a:b
int set[50005];
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
int isUnion(int a,int b,int* set)
{
	return getParent(a,set)==getParent(b,set);
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
int main()
{
	int c,i,k,n,m;
	scanf("%d %d",&n,&m);
	c = 1;
	while(n||m)
	{
		for(i=1;i<=n;i++)
			set[i]=i;
		while(m--)
		{
			scanf("%d %d",&i,&k);
			makeUnion(i,k,set);
		}
		m=0;
		for(k=1;k<=n;k++)
			m+=(getParent(k,set)==k);
		printf("Case %d: %d\n",c++,m);
		scanf("%d %d",&n,&m);
	}
	return 0;
}

Posted August 19, 2011 by epicrado in Union find

UVA – 10608 – Friends   Leave a comment


#include <stdio.h>
#define max(a,b) (a>b)?a:b
int set[30005];
int count[30005];
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
int isUnion(int a,int b,int* set)
{
	return getParent(a,set)==getParent(b,set);
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
int main()
{
	int c,i,k,n,m;
	scanf("%d",&c);
	while(c--)
	{
		scanf("%d %d",&n,&m);
		for(i=1;i<=n;i++)
			count[set[i]=i]=0;
		while(m--)
		{
			scanf("%d %d",&i,&k);
			makeUnion(i,k,set);
		}
		for(k=1;k<=n;k++)
			count[getParent(k,set)]++;
		m=1;
		for(i=1;i<=n;i++)m=max(m,count[i]);
		printf("%d\n",m);
	}
	return 0;
}

Posted August 19, 2011 by epicrado in Union find