| 火影忍者之～忍者村 | ||||||
| ||||||
| 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 |
题解：并查集+hash的map表达
#include <iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<algorithm> #include<map> using namespace std; int n,l; map<string,int> mp; int team[3005]; char ch1[15],ch2[15],ch3[15]; int num(char *s) {map<string,int>::iterator it;it=mp.find(s);if (it!=mp.end()) return it->second;else {mp[s]=++l; team[l]=l; return l;} } int findteam(int k) {if (team[k]!=k){team[k]=findteam(team[k]);return team[k];}else return team[k]; } int main() {while(~scanf("%d",&n)){mp.clear(); l=0;for(int i=1;i<=n;i++){scanf("%s%s%s",&ch1,&ch2,&ch3);int n1=num(ch1);int n2=num(ch2);int n3=num(ch3);n1=findteam(n1);n2=findteam(n2);n3=findteam(n3);team[n2]=n1;team[n3]=n1;/*if (n1!=n2) team[n2]=n1;if (n1!=n3) team[n3]=n1;if (n2!=n3) team[n3]=n2;这样写就RE了，训练赛时，re到崩溃。这种写法很矛盾吧*/}/*for(int i=1;i<=l;i++) team[i]=findteam(i);sort(team+1,team+1+l);int ans=0;for(int i=1;i<=l;i++)if(team[i]!=team[i-1]) ans++;printf("%d\n",ans);*/set<int> s;for(int i=1;i<=l;i++)s.insert(findteam(team[i]));printf("%d\n",s.size());}return 0; }
