G挂

第一问可以UF？第二问就是一个BFS搜索？对于A的每一个直接相连的node，做一次bfs，然后看看那些点会因为这一条路径被cut而使得抵达他们的path减少，如果变为0 那么这条路径被cut后没法接到消息的node个数+1？

第一问是树，求每个节点的子孙有多少个。
时间复杂度O(n)

第二问是DFS
两个数组value(I)，表示节点I是从A的那个儿子访问到的，初始-1
visited(I)表示I节点是否访问过，初始false
for loop节点A的儿子们：
   reset visited数组全为false
   出发做DFS，经过的每个节点都：
      标记visited true
       如果value为-1，更新为A的当前儿子的值
       否则，更新为-2
最后找出谁最多就是答案，这里面也可以另外弄个数组记录每个儿子节点的染色个数，最后就不用再统计一遍了。
时间复杂度O(n^2)

jackalsin 发表于 2019-2-4 08:57
楼主，能问一下A一定是消息源么？

嗯……一定有且只有一个信息源。
你可以定为A，也可以定为B……啥名都行，我跟面试官讨论了下他说你定吧。于是我就定A了。
//感觉这个细节和题没啥关系

xh_pku 发表于 2019-2-4 08:29
这题我觉得，假设A的neighbor 为集合nA,先把所有有两条路径的节点全部去掉，然后在看单独通过nA中每个节点 ...

为啥是把有2条路径的都去掉，我觉得是≥2条吧……

杨超越 发表于 2019-2-4 10:03
不好意思 我没明白“如果每个人至多从一个人那里得到消息” 这是什么意思。。这个限制条件有和没有有什么区 ...

感觉也没啥特别多，就是图与树的区别

杨超越 发表于 2019-2-4 10:03
不好意思 我没明白“如果每个人至多从一个人那里得到消息” 这是什么意思。。这个限制条件有和没有有什么区 ...

同问。。。。。。

henear 发表于 2019/02/04 11:22:38


为啥是把有2条路径的都去掉，我觉得是≥2条吧……

对的 我说错了

第二问我觉得可以DFS，只要那个节点的indegree > 1 就可以直接返回，因为说明肯定有其他的path能够传递信息到这个节点。统计一下A到某个直接子节点这条path断掉后 会让多少个node的indegree 变成0 ，选最大的那个？

pengdu 发表于 2019/02/04 10:38:15
第一问是树，求每个节点的子孙有多少个。
时间复杂度O(n)

第二问是DFS
两个数组value(I)，表示节点I是从A的那个儿子访问到的，初始-1
visited(I)表示I节点是否访问过，初始fa...

我觉得pengdu的解法是对的。这个解法关键在于找出有两条及以上信息来源的子节点，然后在统计总数目的时候予以剔除。我们是不是还可以进一步将算法优化一下，第一次发现两条信息子节点时，我们可以把该子节点的所有子节点全部标记为-2，之后再dfs遇到这类-2子节点，我们直接返回即可。另外，我觉得时间复杂度有点小问题，o（V+E）square 更为精确，因为这里Ｅ可能会是V square。

richpanda 发表于 2019/02/05 03:56:09


我觉得pengdu的解法是对的。这个解法关键在于找出有两条及以上信息来源的子节点，然后在统计总数目的时候予以剔除。我们是不是还可以进一步将算法优化一下，第一次发现两条信息子节点时，我们可以把该子节...

我错了，这里时间复杂度没有问题。他这个解法是O（V2+E），所以O（n2）没有问题。