题目链接：http://acm.swust.edu.cn/problem/772/
Time limit(ms): 1000 Memory limit(kb): 65535
Description
每个人都有朋友，朋友也有很多种，比如：
石友－－情谊坚贞的朋友。
挚友－－志同道合的朋友。
益友－－于己有帮助的朋友。
闺友－－闺房中无话不谈的朋友。
君子交：指道义之交，即在道义上相互支持的朋友。
竹马之交：少年时骑竹马为戏的朋友，指自幼相交的朋友，等等。
现在dearway定义如果王二和张三是朋友，李四和张三也是朋友，那么王二和李四也是朋友，即朋友具有传递关系。现在给你N种朋友关系，问你有多种朋友集合，这些集合里不会出现两个朋友来自两个不同的集合。
Input
多组数据输入（小于等于10组）。每组数据第一行为一个整数N（ 1 <= N <= 1000）表示N种朋友关系，接下来N行，每行首先输入一个整数ni( 1 <= ni <= 10)表示该种朋友关系中包含ni个人。然后ni个字符串，每个字符串由52个大小写英文字母及数字组成且长度小于10，表示ni个不同的人。
Output
每组数据输出一行，表示满足要求的答案。
Sample Input
|
4
2 Hilary Dearway
1 Hilary
2 Rusty Serena
2 Serena Luoxi
10
2 a b
2 b c
1 c
3 a d e
2 e f
2 f g
2 g h
2 h i
2 j k
1 z
|
Sample Output
|
2
3
|
解题思路：一个并查集问题，每输入一个集合，朋友集合种类+1,然后并查集合并，看是否能合并到一个集合(种类-1)，由于字符串不太好操作
利用map强大的字符处理能力，把字符串一一对应成数字进行操作，具体的看代码吧~~~
代码入下：
#include<iostream>
#include<map>
#include<string>
using namespace std;
#define maxn 10001
map<string, int>mpt;
int father[maxn], ans, n, cnt, num;
void init(){
mpt.clear();
cnt = ans = ;
for (int i = ; i < maxn; i++)
father[i] = i;
}
int findset(int x){
return father[x] != x ? father[x] = findset(father[x]) : father[x];
}
void mergy(int a, int b){
int x = findset(a), y = findset(b);
if (x == y) return;
else{
father[x] = y;
ans--;
}
}
int main(){
string s;
while (cin >> n){
init();
for (int i = ; i <= n; i++){
int a, b;
cin >> num >> s;
if (!mpt[s]){
a = ++cnt;
mpt[s] = cnt;
ans++;
}
else a = mpt[s];
for (int j = ; j < num; j++){
cin >> s;
if (!mpt[s]){
b = ++cnt;
mpt[s] = cnt;
ans++;
mergy(a, b);
}
else{
b = mpt[s];
mergy(a, b);
}
}
}
cout << ans << endl;
}
return ;
}