【并查集】 HDU 3172 Virtual Friends

本文主要是介绍【并查集】 HDU 3172 Virtual Friends，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU 3172 Virtual Friends

数据量大，不建议用cin。

#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <cstring>
#include <stdlib.h>
#include <map>
using namespace std;map <string, int > g;char s1[30], s2[30];
int fa[100005], sum[100005];int findd(int x)
{if(x != fa[x])fa[x] = findd(fa[x]);return fa[x];
}int main()
{int t;while(scanf("%d", &t) != EOF){while(t--){int m;scanf("%d", &m);getchar();g.clear();for(int i = 0; i <= 100005; i++) fa[i] = i;int num = 0;while(m--){scanf("%s%s", s1, s2);string s = s1;if(g.find(s) == g.end()){num++;g[s] = num;sum[num] = 1;}string ss = s2;if(g.find(ss) == g.end()){num++;g[ss] = num;sum[num] = 1;}int a = findd(g[s]), b = findd(g[ss]);if(a != b){fa[a] = b;sum[b] += sum[a];}printf("%d\n", sum[b]);}}}return 0;
}

这篇关于【并查集】 HDU 3172 Virtual Friends的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---