原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=3172
并查集的运用。。。
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<map> 6 using std::map; 7 using std::string; 8 const int Max_N = 100010; 9 struct UnionFind { 10 map<string, int> rec; 11 int num[Max_N], par[Max_N]; 12 void init() { 13 for (int i = 1; i < Max_N; i++) { 14 par[i] = i; 15 num[i] = 1; 16 } 17 rec.clear(); 18 } 19 inline int find(int x) { 20 while (x != par[x]) { 21 x = par[x] = par[par[x]]; 22 } 23 return x; 24 } 25 inline void unite(int x, int y) { 26 x = find(x), y = find(y); 27 if (x != y){ 28 par[x] = y; 29 num[y] += num[x]; 30 printf("%d ", num[y]); 31 } else { 32 printf("%d ", num[y]); 33 } 34 } 35 inline void gogo() { 36 int n, cnt = 1; 37 char s1[100], s2[100]; 38 scanf("%d", &n); 39 while (n--) { 40 scanf("%s %s", s1, s2); 41 if (!rec[s1]) rec[s1] = cnt++; 42 if (!rec[s2]) rec[s2] = cnt++; 43 unite(rec[s1], rec[s2]); 44 } 45 } 46 }ans; 47 int main() { 48 #ifdef LOCAL 49 freopen("in.txt", "r", stdin); 50 freopen("out.txt", "w+", stdout); 51 #endif 52 int t; 53 while (~scanf("%d", &t)) { 54 while (t--) ans.init(), ans.gogo(); 55 } 56 return 0; 57 }