本文主要是介绍HDU-3172 Virtual Friends 并查集+map，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int maxn = 100050;
const int inf = 1<<30;
int n,m;
int p[maxn],mark[maxn];
map<string,int>maps;
int find(int x)
{ return x!=p[x]?p[x]=find(p[x]):x;
}
void merge( int a,int b )
{int x = find(a);int y = find(b);if( x != y ){p[x] = y;mark[y] += mark[x];printf("%d\n",mark[y]);}elseprintf("%d\n",mark[y]);
}
void init()
{maps.clear();for( int i = 1; i < maxn; i ++ ){p[i] = i;mark[i] = 1;}
}
int main()
{//freopen("data.txt","r",stdin); int cas,pos;string s1,s2;while( scanf("%d",&cas) != EOF ){while( cas -- ){init();pos = 1;scanf("%d",&n);for( int i = 0; i < n; i ++ ){cin>>s1>>s2;if( !maps[s1] )maps[s1] = pos ++;if( !maps[s2] )maps[s2] = pos ++;merge(maps[s1],maps[s2]);}}}return 0;
}这篇关于HDU-3172 Virtual Friends 并查集+map的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
