InputInput 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).OutputWhenever a friendship is formed, print a line containing one integer, the number of people in the social network of the two people who have just become friends.Sample Input
1 3 Fred Barney Barney Betty Betty Wilma
Sample Output
2 3 4
题解：带权并查集 可以记录每个集合中元素的个数
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <vector> 6 #include <cstdlib> 7 #include <iomanip> 8 #include <cmath> 9 #include <ctime> 10 #include <map> 11 #include <set> 12 #include <queue> 13 using namespace std; 14 #define lowbit(x) (x&(-x)) 15 #define max(x,y) (x>y?x:y) 16 #define min(x,y) (x<y?x:y) 17 #define MAX 100000000000000000 18 #define MOD 1000000007 19 #define pi acos(-1.0) 20 #define ei exp(1) 21 #define PI 3.141592653589793238462 22 #define INF 0x3f3f3f3f3f 23 #define mem(a) (memset(a,0,sizeof(a))) 24 typedef long long ll; 25 ll gcd(ll a,ll b){ 26 return b?gcd(b,a%b):a; 27 } 28 const int N=100100; 29 const int mod=1e9+7; 30 map<string,int> mp; 31 int sum[N],f[N]; 32 void init() 33 { 34 for(int i=1;i<N;i++) 35 f[i]=i,sum[i]=1; 36 } 37 int Find(int x) 38 { 39 if(x!=f[x]) 40 f[x]=Find(f[x]); 41 return f[x]; 42 } 43 int Union(int a,int b) 44 { 45 int p=Find(a); 46 int q=Find(b); 47 if(p!=q){ 48 f[p]=q; 49 sum[q]+=sum[p]; 50 } 51 return sum[q]; 52 } 53 int main() 54 { 55 int t,n; 56 while(scanf("%d",&t)!=EOF){ 57 while(t--){ 58 mp.clear(); 59 scanf("%d",&n); 60 init(); 61 int num=1; 62 char a[25],b[25]; 63 while(n--){ 64 int u,v; 65 scanf("%s%s",a,b); 66 if(mp[a]==0) mp[a]=num++; 67 if(mp[b]==0) mp[b]=num++; 68 u=mp[a],v=mp[b]; 69 int k=Union(u,v); 70 printf("%d\n",k); 71 } 72 } 73 } 74 return 0; 75 }
HDU 3172 Virtual Friends （map+并查集）
原文：http://www.cnblogs.com/shixinzei/p/7294917.html