Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1626
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){
pars.clear();
groupSize.clear();
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;
join(a,b>;
}
cout << best << endl;
}
}
Input
caterpillar
bird
horse
elefant
herb
herb caterpillar
caterpillar bird
0 0
Output
Demonstration
UVA Online Judge solution - 10685-Nature - UVA Online Judge solution in C,C++,java