哈理工1311 并查集+map火影忍者之～忍者村

火影忍者之～忍者村

Time Limit: 2000 MS Memory Limit: 65536 K Total Submit: 210(74 users) Total Accepted: 119(69 users) Rating:  Special Judge: No

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

#include<stdio.h>
#include<iostream>
#include<map>
#include<string.h>
using namespace std;
int f[3005];
void init(int t)
{
    for(int i=0;i<=t*3;i++)
    f[i]=i;
}
int find(int x)
{
    return f[x] == x ? x : (f[x] = find(f[x]));
}
void merge(int a,int b)
{
    int A,B;
    A=find(a);
    B=find(b);
    if(A!=B)
    f[B]=A;
}
int main()
{
    int t;
    while(~scanf("%d",&t))
    {
        map<string,int>a;
        int cont=1;
        init(t);
        for(int i=0;i<t;i++)
        {
            char b[3][20];
            for(int j=0;j<3;j++)
            {
                scanf("%s",b[j]);
                if(a[b[j]]==0){a[b[j]]=cont;cont++;}
            }
            merge(a[b[0]],a[b[1]]);
            merge(a[b[0]],a[b[2]]);
        }
        int output=0;
        for(int i=0;i<cont;i++)
        {
            if(i==f[i])output++;
        }
        printf("%d\n",output-1);
    }
}