Archive for the ‘Graph related’ 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