本文主要是介绍HRBUST1311-火影忍者之～忍者村，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| 火影忍者之～忍者村 | ||||||
| ||||||
| Description | ||||||
| 忍者村是忍者聚居的村子，相等于国家的军事力量。绝大部分村民都是忍者，有一些忍者会在村内开设书店、餐厅等，不过大部分忍者都是为村子执行任务的忍者，以赚取酬劳，并于战时为国家出战。村子亦会培训年轻村民成为忍者。 忍者们一般以三人一组执行各种任务，现在假设不同村子的忍者不会一起执行任务，给出一些忍者的组合，判断由这些组合能确定的最多的忍者村的个数。
| ||||||
| Input | ||||||
| 第一行是整数n，表示已知n组忍者组合，接下来n行每行三个忍者的名字，n不超过1000，每个名字不长于10. | ||||||
| Output | ||||||
| 对于每组输入，输出在这些忍者最多属于多少个忍者村。 | ||||||
| Sample Input | ||||||
| 7 a b c c d e d e f g k h l m n o p q h r p | ||||||
| Sample Output | ||||||
| 3 | ||||||
| Source | ||||||
| 2012 Spring Contest 3 - STL | ||||||
| Author | ||||||
| 拂晓 |
解题思路：并查集
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <climits>using namespace std;#define LL long long
const int INF=0x3f3f3f3f;char b[3][20];
int f[3005];int Find(int x)
{return f[x]==x?x:(f[x]=Find(f[x]));
}int main()
{int n;while(~scanf("%d",&n)){map<string,int>a;int cnt=1;for(int i=0;i<=3*n;i++) f[i]=i;for(int i=0;i<n;i++){for(int j=0;j<3;j++){scanf("%s",b[j]);if(a[b[j]]==0) a[b[j]]=cnt++;}int aa=Find(a[b[0]]),bb=Find(a[b[1]]);if(aa!=bb) f[aa]=bb;aa=Find(a[b[0]]),bb=Find(a[b[2]]);if(aa!=bb) f[aa]=bb;}int sum=0;for(int i=1;i<cnt;i++)if(i==f[i]) sum++;printf("%d\n",sum);}
}这篇关于HRBUST1311-火影忍者之～忍者村的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
