英语中,有些单词可以出现在其他单词后面。例如“Love”可以出现在“I”之后,“You”可以出现在“Love”之后,因此它们能构成“I Love You”这句话。 现在给你一些单词间的关系,你能计算出最多能有几个单词组合在一起构成一句话吗? 输入描述: 输入包含多组数据。每组数据的第一行包含一个正整数n (1≤n≤10000)。紧接着n行单词关系,每行包含两个单词A和B,表示单词B能出现在A后面。单词长度不超过32个字符,并且只有字母组成。不存在循环的依赖关系。 输出描述: 对应每组数据,输出最多有几个单词能构成一个句子。 输入例子: 1hello world3I lovelove youlove me 输出例子: 23
用set和map可以很轻松的解决
#include
#include
#include
#include
using namespace std;
int getLen(string s,map
mp,map
if(hasFind.count(s)==1)
return hasFind[s];
if(mp.count(s)==0)
return 1;
int len=0;
int max=0;
for(set
iter=mp[s].begin();iter!=mp[s].end();iter++)
{
len=1+getLen(*iter,mp,hasFind);
if(len>max)
max=len;
}
hasFind[s]=max;
return max;
}
int main(){
string s1,s2;
int n;
while(cin>>n){
map
map
while(n-->0){
cin>>s1>>s2;
mp[s1].insert(s2);
}
int max=0;
int len;
for(map
it=mp.begin();it!=mp.end();it++){
if((len=getLen(it->first,mp,hasFind))>max)
max=len;
}
cout< } return 0; }