本文主要是介绍HRBUST1311 火影忍者之~忍者村,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
火影忍者之~忍者村
忍者村是忍者聚居的村子,相等于国家的军事力量。绝大部分村民都是忍者,有一些忍者会在村内开设书店、餐厅等,不过大部分忍者都是为村子执行任务的忍者,以赚取酬劳,并于战时为国家出战。村子亦会培训年轻村民成为忍者。
忍者们一般以三人一组执行各种任务,现在假设不同村子的忍者不会一起执行任务,给出一些忍者的组合,判断由这些组合能确定的最多的忍者村的个数。
7
a b c
c d e
d e f
g k h
l m n
o p q
h r p
—————————————————————————————————————
并查集,把相同的连边
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include <map>
using namespace std;map<string,int>mp;
string s[10];
int pre[3005];void init()
{for(int i=0; i<3004; i++)pre[i]=i;
}int fin(int x)
{if(x!=pre[x])return pre[x]=fin(pre[x]);return pre[x];
}int main()
{int n;while(~scanf("%d",&n)){init();int cnt=0;mp.clear();for(int i=0; i<n; i++){for(int j=0; j<3; j++){cin>>s[j];if(!mp.count(s[j])){mp[s[j]]=cnt++;}}int a=fin(mp[s[0]]);int b=fin(mp[s[1]]);if(a!=b){pre[a]=b;}a=fin(mp[s[0]]);b=fin(mp[s[2]]);if(a!=b){pre[a]=b;}}int ans=0;for(int i=0; i<cnt; i++){if(pre[i]==i)ans++;}printf("%d\n",ans);}return 0;
}
这篇关于HRBUST1311 火影忍者之~忍者村的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!