首页 > ACM题库 > HDU-杭电 > HDU 3172-Virtual Friends-并查集-[解题报告]HOJ
2014
03-06

HDU 3172-Virtual Friends-并查集-[解题报告]HOJ

Virtual Friends

问题描述 :

These days, you can do all sorts of things online. For example, you can use various websites to make virtual friends. For some people, growing their social network (their friends, their friends’ friends, their friends’ friends’ friends, and so on), has become an addictive hobby. Just as some people collect stamps, other people collect virtual friends.

Your task is to observe the interactions on such a website and keep track of the size of each person’s network.

Assume that every friendship is mutual. If Fred is Barney’s friend, then Barney is also Fred’s friend.

输入:

Input file contains multiple test cases.
The first line of each case indicates the number of test friendship nest.
each friendship nest begins with a line containing an integer F, the number of friendships formed in this frindship nest, which is no more than 100 000. Each of the following F lines contains the names of two people who have just become friends, separated by a space. A name is a string of 1 to 20 letters (uppercase or lowercase).

输出:

Input file contains multiple test cases.
The first line of each case indicates the number of test friendship nest.
each friendship nest begins with a line containing an integer F, the number of friendships formed in this frindship nest, which is no more than 100 000. Each of the following F lines contains the names of two people who have just become friends, separated by a space. A name is a string of 1 to 20 letters (uppercase or lowercase).

样例输入:

1
3
Fred Barney
Barney Betty
Betty Wilma

样例输出:

2
3
4

/*
分析:
    哇塞~,不看不知道,一看吓一跳耶~,用C提交的我又是
第一耶~,哎~没法儿啊,谁让就我一人用C写的呢……

    并查集&&字典树。用字典树给单词编号,用并查集~……,
不用说了吧~,你懂我懂大家懂的事儿~ – -I

                                           2012-07-17
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"


struct A
{
	int pre;
	int total;
}E[100011];
int k;


struct dictree
{
	struct dictree *child[52];
	int flag;
};
struct dictree *root;


void insert(char *str)
{
	struct dictree *now,*next;
	int i,j;
	int len;
	int temp;


	now=root;
	len=strlen(str);
	for(i=0;i<len;i++)
	{
		temp=str[i]-'A';
		if(now->child[temp])
			now=now->child[temp];
		else
		{
			next=(struct dictree *)malloc(sizeof(struct dictree));
			for(j=0;j<52;j++)	next->child[j]=0;
			next->flag=0;
			now->child[temp]=next;
			now=next;
		}
	}
	now->flag=k;
	E[k].pre=k;
	E[k].total=1;
	k++;
}
int f_tree(char *str)
{
	struct dictree *next;
	int i;
	int len;
	int temp;


	len=strlen(str);
	next=root;
	for(i=0;i<len;i++)
	{
		temp=str[i]-'A';
		if(next->child[temp])
			next=next->child[temp];
		else return 0;
	}
	return next->flag;
}




int f_u(int k)
{
	if(E[k].pre==k)	return k;
	E[k].pre=f_u(E[k].pre);
	return E[k].pre;
}
void Union(int f1,int f2)
{
	E[f1].pre=f2;
	E[f2].total+=E[f1].total;
}


int main()
{
	int T;
	int n;
	int i;
	int f1,f2;
	int a,b;
	char str1[25],str2[25];


	while(scanf("%d",&T)!=-1)
	{
		while(T--)
		{
			scanf("%d",&n);


			root=(struct dictree *)malloc(sizeof(struct dictree));
			for(i=0;i<52;i++)	root->child[i]=0;
			root->flag=0;


			k=1;
			while(n--)
			{
				scanf("%s%s",str1,str2);
				for(i=0;str1[i];i++)	if(str1[i]>='a')	str1[i]-=6;
				for(i=0;str2[i];i++)	if(str2[i]>='a')	str2[i]-=6;
				a=f_tree(str1);
				b=f_tree(str2);
				if(a==0)	{a=k;insert(str1);}
				if(b==0)	{b=k;insert(str2);}


				f1=f_u(a);
				f2=f_u(b);
				if(f1!=f2)	Union(f1,f2);
				printf("%d\n",E[f2].total);
			}
		}
	}
	return 0;
}

参考:http://blog.csdn.net/ice_crazy/article/details/7756009


  1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.