计蒜客 网络交友

题目：在网络社交的过程中，通过朋友，也能认识新的朋友。在某个朋友关系图中，假定 A 和 B 是朋友，B 和 C 是朋友，那么 A 和 C 也会成为朋友。即，我们规定朋友的朋友也是朋友。

现在要求你每当有一对新的朋友认识的时候，你需要计算两人的朋友圈合并以后的大小。 
输入格式

第一行：一个整数 n(n\leq 5000)n(n≤5000)，表示有 nn 对朋友认识。

接下来 nn 行：每行输入两个名字。表示新认识的两人的名字，用空格隔开。（名字是一个首字母大写后面全是小写字母且长度不超过 20 的串）。

输出格式

对于每一对新认识的朋友，输出合并以后的朋友圈的大小。

样例输入

3 
Fred Barney 
Barney Betty 
Betty Wilma 
样例输出

2 
3 

4

#include<iostream>
#include<cstdio>
#include<set>
#include<map>;
#include<string>
using namespace std;
int father[10010];
int size[10010];
int n;
void init(){
	for(int i = 1;i <= 10000;i ++){
		father[i] = i;
		size[i] = 1;
	}
}

int get(int x){
	if(father[x] == x){
		return x;
	}
	int y = father[x];
	father[x] = get(y);
	return father[x];
}

void merge(int x,int y){
	int m = get(x);
	int n = get(y);
	if(n != m){
		father[n] = m;
		size[m] += size[n];
	}
}

int main(){
	scanf("%d",&n);
	
	set<string> se;
	map<string,int>mp;
	int p = 1;
	char a[25],b[25];
	
	init();
	while(n--){
		scanf("%s%s",&a,&b);
		
		if(!se.count(a)){
			se.insert(a);
			mp[a] = p++;
		}
		if(!se.count(b)){
			se.insert(b);
			mp[b] = p++;
		}
		
		int ans = 0;
		merge(mp[a],mp[b]);
		ans = size[get(mp[b])];
		printf("%d\n",ans);
	
	}
	return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：计蒜客 网络交友，转载请注明来源！