解題思路：典型的并查集，只是每個人的名字要轉(zhuǎn)換成數(shù)字，可以用map，也可以用字典樹，我最開始用的字典樹結(jié)果爆內(nèi)存了。。

爆內(nèi)存：

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 200000; int n,fa[maxn],trie[maxn][52],cnt,id[2000000],num; int tot[maxn]; char str[2][20];void init() {for(int i = 0; i <= 2*n; i++){fa[i] = i;tot[i] = 1;}memset(id,-1,sizeof(id));memset(trie,-1,sizeof(trie));cnt = num = 0; }int insert(char *s) {int p = 0,idx;while(*s != 0){if(*s >= 'A' && *s <= 'Z') idx = *s - 'A' + 26;else idx = *s - 'a';if(trie[p][idx] == -1)trie[p][idx] = ++cnt;p = trie[p][idx];s++;}if(id[p] == -1)id[p] = ++num;return id[p]; }int find(int x) {if(fa[x] == x) return x;return fa[x] = find(fa[x]); }int main() {int t,x,y,fx,fy;scanf("%d",&t);while(t--){scanf("%d",&n);init();for(int i = 1; i <= n; i++){scanf("%s %s",str[0],str[1]);x = insert(str[0]);y = insert(str[1]);fx = find(x); fy = find(y);if(fx != fy){fa[fy] = fx;tot[fx] += tot[fy];}printf("%d\n",tot[fx]);}}return 0; }

別人的：

#include<stdio.h> #include<map> #include<iostream> using namespace std; map<string,int> m; int set[100005]; int num[100005]; int find(int x) {int r=x;while(r!=set[r])r=set[r];int i=x;while(i!=r){int j=set[i];set[i]=r;i=j;}return r; } void merge(int x,int y) {int fx=find(x);int fy=find(y);if(fx!=fy){set[fx]=fy;num[fy]+=num[fx];printf("%d\n",num[fy]);}else{printf("%d\n",num[fy]);} } int main() {int t;char a[25];char b[25];while(scanf("%d",&t)!=EOF){while(t--){int n;scanf("%d",&n);for(int i=1;i<100005;i++){set[i]=i;num[i]=1;}m.clear();int ans=1;for(int i=1;i<=n;i++){scanf("%s%s",a,b);if(!m[a]){m[a]=ans++;}if(!m[b]){m[b]=ans++;}merge(m[a],m[b]);}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 3172(并查集+hash)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。