GG电面GG，感觉有点奇怪

同问follow up什么思路？我的想法是，如果a和b在同一个图里，和之前做法一样，如果在不同图里，b的点数是这个图中的节点数，然后取这两种情况的max。不知楼主是什么做的？

写了一个模拟答案，思路是按照二楼大神取 拥有最大儿子数目的子树 请各位看看有啥问题不
class GraphNode {
public:
    vector<GraphNode*> neighbors;
    int val;
    GraphNode(int val) {
        this->val = val;
    }  
};

GraphNode* chooseMaxNode(vector<GraphNode*> allNodes, GraphNode* a) {
    GraphNode* b;
    int maxChildren = 0;
    for (GraphNode* node : a->neighbors) {
        int curChildren = getChildrenNumber(node);
        if (curChildren > maxChildren) {
            maxChildren = curChildren;
            b = node;
        }
    }
    return b;
}

int getChildrenNumber(GraphNode* root) {
    if (!root) {
        return 0;
    }

    int res = 0;
    for (GraphNode* child : root->neighbors) {
        res += getChildrenNumber(child);
    }
    return res + 1;
}

ziwei1992 发表于 2019-2-7 13:06
同问follow up什么思路？我的想法是，如果a和b在同一个图里，和之前做法一样，如果在不同图里，b的点数是这 ...

对我就是这么做的

mwen2 发表于 2019-2-7 04:52
求问一下楼主能share一下代码嘛？多谢多谢~

不好意思没有copy代码

ziwei1992 发表于 2019/02/07 13:06:00
同问follow up什么思路？我的想法是，如果a和b在同一个图里，和之前做法一样，如果在不同图里，b的点数是这个图中的节点数，然后取这两种情况的max。不知楼主是什么做的？

如果在不同图里，b的点数不应该是所有图中节点数最多的那个吗？能再详细说下你的思路吗？

naihe1990 发表于 2019-2-7 23:47
如果在不同图里，b的点数不应该是所有图中节点数最多的那个吗？能再详细说下你的思路吗？

嗯嗯就是这个意思

这题理解了题义了就很简单吧。因为a和b都只能走自己走过的相邻点，这样最后走下来ab占领的点都是一个connected component。所以b就选a的初始点的一个相邻点，并且以这个相邻点为root的子节点（仅限那个分支）总数目最多。这样a就没法干涉后面轮b选点了。不过这好像有个bug，如果a那边点已经选完了，游戏是不是算结束？这样b也无法选点了。如果是这样的话，那么情况有些复杂。follow up意义不大，就是把其它几个单独分开的connected component也算一下大小，取一下最大值。

按照你的描述，可以继续占领之前占领的某点相邻，也就是说如果a选完一支还能继续选另一支？那即使b选了最多子孩子的一支开头，也不一定敌的过a把其他所有支占领了。所以是有什么终止条件吗？

如果不能重复占领的话，需要考虑A 的subtree之外的节点数目之和。
如果A subtree之外的节点数量比A subtree多的话，直接可以占领A的父节点。 因为在不能重复占领的情况下，这样直接就赢了。（A只能在自己的subtree挣扎）
如果少的话，就选取A子节点中最大的subtree（节点数目最多）

计算节点数量就是个基本功了，BFS, DFS都没问题吧