The Republic of Tsay is one of the most well-known countries in the world. There are thousands of cities and some highway connections between cities. There is exactly one path formed by highways between any two cities, and the length of the highway connecting the two cities is 1. Your mission is to find the longest path out of them.
You may use the code template below and replace /*TODO*/ section with your code.
#include <iostream>
#include <deque>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#define MAX 2000
using namespace std;
deque<int> F[MAX];
vector<string> name;
vector<string>::iterator it;
int V[MAX];
int n,k,md;
int getCityIndex(string p){
int ct;
it = find(name.begin(),name.end(),p);
if (it < name.end()) return it-name.begin();
else if (it == name.end()){
name.push_back(p);
return name.size()-1;
}
}
void DFS(int x,int level){
/*TODO*/
}
int main(){
string x,y;
int a,b;
cin >> n;
md = 0;
name.clear();
for(int i = 0;i < n;i++){
F[i].clear();
V[i]=0;
}
while(1){
cin >> x >> y;
if ((x == "=") && (y == "=")) break;
a = getCityIndex(x);
b = getCityIndex(y);
F[a].push_back(b);
F[b].push_back(a);
}
for(int i = 0;i < n;i++){
if (F[i].size() != 1) continue;
memset(V,0,sizeof(V));
V[i] = 1;
DFS(i,0);
}
cout << md;
}
Input the number of cities n, and the size of n will not exceed 2000. Then, input two city names in each line which means a highway connection between these two cities. The city name will not exceed 100 characters and does not contain blank. When the two city names are "=", it means that the data input is completed, and does not include the last line in the processing.
Output the value of the longest path.