HRBUST1311 火影忍者之～忍者村 2017-03-06 16:06 106人阅读 评论(0) 收藏

火影忍者之～忍者村

 

忍者村是忍者聚居的村子，相等于国家的军事力量。绝大部分村民都是忍者，有一些忍者会在村内开设书店、餐厅等，不过大部分忍者都是为村子执行任务的忍者，以赚取酬劳，并于战时为国家出战。村子亦会培训年轻村民成为忍者。

忍者们一般以三人一组执行各种任务，现在假设不同村子的忍者不会一起执行任务，给出一些忍者的组合，判断由这些组合能确定的最多的忍者村的个数。

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

—————————————————————————————————————

并查集，把相同的连边

#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;

}