c++ - 在老板层次结构中查找 "top"老板仅适用于某些测试用例

Question

更新:

我已经修复了代码，所以我能想出的每个测试用例都给了我正确的结果，但我仍然遗漏了一些东西，因为在线法官仍然说它是错误的。我在本段之后立即包含了代码。我知道我采用的方法很丑陋而且效率不高，但我不在乎。我现在只想让它输出正确的答案。

#include <iostream>
#include <map>
#include <string>
#include <queue>

using namespace std;

int main()
{
map<string, string> names;
map<string, int > bossCount;

vector<string> bosses;
string topBoss;
int n;
int max = 0;

cin >> n;

for (int i = 0; i < n; i++)
{
    bool add = true;
    string c1, c2;
    cin >> c1 >> c2;
    names[c1] = c2;
    for (int i = 0; i < bosses.size(); i++)
    {
        if (bosses[i] == c2)
            add = false;
        //bosses.push_back(c2);
    }
    if (add == true)
        bosses.push_back(c2);
}

for (map<string, string>::iterator it = names.begin(); it != names.end(); it++)
    for(int i = 0; i < bosses.size(); i++)
    {
        if (bosses[i] == (*it).second)
        {
            bossCount[bosses[i]]++;
        }
    }

for (map<string, string>::iterator it = names.begin(); it != names.end(); it++)
    for (int i = 0; i < bosses.size(); i++)
    {
        if (bosses[i] == (*it).first)
        {
            bossCount[bosses[i]] = 0;
            bossCount[(*it).second]++;
        }
    }

for (map<string, int>::iterator it = bossCount.begin(); it != bossCount.end(); it++)
{
    if((*it).second == max)
    {
        if ((*it).first < topBoss)
            topBoss = (*it).first;
    }

    if ((*it).second > max)
    {
        max = (*it).second;
        topBoss = (*it).first;
    }       
}   

cout << topBoss;

return 0;
}

我得到了一个列表，其中包含唯一名称和他们向其报告的老板(老板不是唯一的)。然后我必须找到哪个老板拥有最高等级。这意味着，列表中的几个第一个唯一名称可能有相同的老板，但是那个老板可能有他自己的老板，这意味着第一个唯一名称回答他们老板的老板，所以老板的老板赢得了层次结构。这是整个问题:http://i.imgur.com/nyTgW.png

我已经编写了代码，它可以在问题中提供的示例测试用例中运行(输出 Napoleon)。它也适用于我抛给它的其他一些测试用例，但是当我使用这个测试用例时它不起作用，例如:

4
a b
c b
d b
b e

我认为正确答案应该是“e”，因为“b”的老板是“e”。我的程序在此测试用例中输出 b。有人可以帮助发现这里的问题吗？

#include <iostream>
#include <map>
#include <string>
#include <queue>

using namespace std;

int main()
{
map<string, string> names;
map<string, int > bossCount;

queue<string> next;
vector<string> bosses;
string topBoss;
    int n;
int max = 0;

cin >> n;

for (int i = 0; i < n; i++)
{
    string c1, c2;
    cin >> c1 >> c2;
    names[c1] = c2;
    bosses.push_back(c2);
}

for (map<string, string>::iterator it = names.begin(); it != names.end(); it++)
    for(int i = 0; i < bosses.size(); i++)
    {
        if (bosses[i] != (*it).first)
        {
            bossCount[bosses[i]]++;
        }
    }

for (map<string, int>::iterator it = bossCount.begin(); it != bossCount.end(); it++)
{
    if((*it).second == max)
    {
        if ((*it).first < topBoss)
            topBoss = (*it).first;
    }

    else if ((*it).second > max)
    {
        max = (*it).second;
        topBoss = (*it).first;
    }


}

cout << topBoss;

return 0;
}

Answer 1

听起来您想为层次结构构建一组树，然后进行深度遍历。

最高老板的唯一候选人是那些没有老板的人。所以数据结构应该很容易记录这个。 (如果层次结构总是只有一个最高老板，那么您可以通过返回没有自己老板的唯一个体来简单地解决问题。)

所以我建议从老板到下属的std::multimap。将 null/空名称放入 map 会返回顶级首领。

保留堆栈或使用函数递归从组织结构图的顶部导航到底部，然后在从底部到顶部的返回过程中添加层次结构的大小。