problem Link  : 

In nature, there are alimentary chains. At the basis of this chain, we generally have the vegetals. Small animals eat those vegetals and bigger animals eat the smaller. There can be cycles in the chain, as when some animal dies he starts a decomposition process which will transform its body into minerals that are a source of energy for the vegetals. In this problem you will have to find the largest alimentary chain for a given group of creatures. You can consider that if A is predator of B then they are in the same chain. Input The input file contains several input sets. The description of each set is given below: Each set starts with two integers C (1 ≤ C ≤ 5000), the number of creatures, and R (0 ≤ R ≤ 5000), the number of relations. Follow C lines with the names of the creatures, each consisting of lower case letters (a, b, . . . , z). No name is longer than 30 letters. Then there will be R lines describing the relations. Each line will have 2 names of creatures, meaning that the second creature is a predator of the first one. You can assume that no creature is a predator of himself. Input is terminated by a set where C = R = 0. This set should not be processed. There is a blank line beteween two input sets. Output For each input set produce one line of output, the size of the largest alimentary chain.

Sample Input 5 2 caterpillar bird horse elefant herb herb caterpillar caterpillar bird 0 0

Sample Output 3

Code Examples

#1 Code Example with C Programming

Code - C Programming

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

unordered_map < string,string> pars;
unordered_map groupSize;
int best;

string udfsFind(string& n){
    return pars[n] == n ? n : pars[n] = udfsFind(pars[n]);

void join(string& a, string& b){
    string parA = udfsFind(a);
    string parB = udfsFind(b);
    if(parA == parB) return;
    groupSize[parA] += groupSize[parB];
    best = max(best, groupSize[parA]);
    pars[parB] = parA;

int main()
    int c,r;
    string a,b;
    while(scanf("%d %d",&c,&r),c||r){
        best = 1;
        for(int i=0;i<c;i++){
            cin >> a;
            pars[a] = a;
            groupSize[a] = 1;
        for(int i=0;i < r;i++){
            cin >> a >> b;
        cout << best << endl;
Copy The Code & Try With Live Editor


5 2
herb caterpillar
caterpillar bird
0 0




 UVA Online Judge solution - 10685-Nature - UVA Online Judge solution in C,C++,java

UVA Online Judge solution - 10684-The jackpot - UVA Online Judge solution in C,C++,java
UVA Online Judge solution - 10689-Yet another Number Sequence - UVA Online Judge solution in C,C++,java