G挂

前几天去G家onsite，其他题都还好，就这个题不是特别会，只想出了DFS的解法，想问问大家有什么更好的。
已知有一消息在一群人中间传播。消息

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

？
做到这里时间就到了，后面可能还有别的follow up但是我没做到。

第一问是树，求每个节点的子孙有多少个。
时间复杂度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)

不好意思 我没明白“如果每个人至多从一个人那里得到消息” 这是什么意思。。这个限制条件有和没有有什么区别吗。。？我没太明白 求解答

限制从之多一个人那里得消息的话传递关系就是一棵树，看A的哪棵子树有最多的结点就好了

xiaozong 发表于 2019-2-4 04:55
限制从之多一个人那里得消息的话传递关系就是一棵树，看A的哪棵子树有最多的结点就好了

其实我是想问第二问的……第二问取消限制以后就不是一棵树了

取消限制过后不是个graph吗？还是可以DFS比较A相连的几个neighbor每个下面的connected nodes size吧

类似topological sort。一个节点没有消息后，对所有的邻居的indegree减1。。。如果是0再加进去。visited过多少0 indegree的就是有多少人收不到消息。。。。

dpsyche13th 发表于 2019-2-4 05:43
取消限制过后不是个graph吗？还是可以DFS比较A相连的几个neighbor每个下面的connected nodes size吧

我当时就那么做的然后复杂度太高了

这题我觉得，假设A的neighbor 为集合nA,先把所有有两条路径的节点全部去掉，然后在看单独通过nA中每个节点的path上面有多少个，O(N) 解法。

楼主，能问一下A一定是消息源么？

这题看上去很像 Minimize Malware Spread II ？