题目大意：给出若干对朋友关系，每给出一对朋友关系，就输出二者所在关系网中的人数。
首先是对每个人编号，使用map简化编号过程，然后就是使用并查集更新集合。要注意的是当给出Ａ和Ｂ的朋友关系时，无论Ａ和Ｂ在此之前是否是朋友（属于同一个集合），都要输出建立关系后的朋友网中的人数。
1 #include <cstdio> 2 #include <iostream> 3 #include <map> 4 #include <string> 5 using namespace std; 6 #define MAXN 100000*2+100 7 typedef map<string, int> msi; 8 9 int p_cnt; // the number of people 10 msi m; 11 int p[MAXN], cnt[MAXN]; // cnt[i] save the number of nodes which root is i 12 13 void add_node(string name) 14 { 15 if (!m.count(name)) 16 { 17 m[name] = p_cnt; 18 p[p_cnt] = p_cnt; 19 cnt[p_cnt] = 1; 20 p_cnt++; 21 } 22 } 23 24 int find(int x) 25 { 26 return (x == p[x]) ? x : p[x] = find(p[x]); 27 } 28 29 int main() 30 { 31 #ifdef LOCAL 32 freopen("in", "r", stdin); 33 #endif 34 int T; 35 scanf("%d", &T); 36 while (T--) 37 { 38 int n; 39 scanf("%d", &n); 40 getchar(); 41 string name1, name2; 42 m.clear(); 43 p_cnt = 0; 44 while (n--) 45 { 46 cin >> name1 >> name2; 47 add_node(name1); 48 add_node(name2); 49 int pa = find(m[name1]); 50 int pb = find(m[name2]); 51 if (pa != pb) 52 { 53 p[pb] = pa; 54 cnt[pa] += cnt[pb]; 55 } 56 printf("%d ", cnt[pa]); 57 } 58 } 59 return 0; 60 }