10685 - Nature

Problem Link


#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
int parent[MAXN];

void opt()
{
    for(int i = 1; i < MAXN; i++)
        parent[i] = i;
}

int find_parent(int x)
{
    if(parent[x]==x)
        return x;
    return parent[x] = find_parent(parent[x]);
}

void make_union(int x, int y)
{
    parent[find_parent(x)] = find_parent(y);
}

bool isUnion(int x, int y)
{
    return find_parent(x) == find_parent(y);
}

int main()
{
    int C, R;
    while(cin>>C>>R && C+R!=0)
    {
        opt();
        map<string, int>mp;
        map<int,int>ans;
        int p = 0, c, mx = 0;
        c = C;
        while(C--)
        {
            string s;
            cin>>s;
            mp[s] = ++p;
        }

        while(R--)
        {
            int a, b;
            string s, predator;
            cin>>s>>predator;
            a = mp[s];
            b = mp[predator];
            make_union(a,b);
        }
        for(int i = 1; i <= c; i++)
        {
            int k = find_parent(i);
            ans[k]++;
            mx = max(mx, ans[k]);
        }
        cout<<mx<<endl;
    }

    return 0;
}