G挂

henear 发表于 2019-2-4 11:20
嗯……一定有且只有一个信息源。
你可以定为A，也可以定为B……啥名都行，我跟面试官讨论了下他说你定吧 ...

如果已知消息源是A的话，可以从A开始建图，然后计算indegree，然后从A dfs，只寻找indegree为1的节点计入能够被砍掉的节点

之所以问A是不是消息源，主要想确定消息源是否能确定，
不然按照你的图，如果有M->E，如果消息源不确定，仅知道A知道这个消息，就不能确定消息源有没有给M传播消息，也就是无法得知E是否能够得到消息（不能确定indegree）

第二问其实就是求A的每个child里面，哪个indegree为1的所有子node数最多，时间复杂度为O(E), 因为DFS只有在indegree为1的情况下才会继续计算该node的indegree为1的子node的数量，其只会被call一次，如果被call多次则与indegree=1相矛盾

你给的例子里面 B和C都可以给E
在第一个条件下这个E点怎么办？没看懂

杨超越 发表于 2019/02/04 10:03:38
不好意思 我没明白“如果每个人至多从一个人那里得到消息” 这是什么意思。。这个限制条件有和没有有什么区别吗。。？我没太明白 求解答

先算一下每个点indegree
然后挨个去掉和A相连的点
再用topo sort看看和A在同一级的点 也就是indegree为0 计算挨个可以去掉多少个
因为同一级的点无法从A得到消息

pandami 发表于 2019-2-5 08:47
先算一下每个点indegree
然后挨个去掉和A相连的点
再用topo sort看看和A在同一级的点 也就是indegree为0  ...

谢谢！，这个题我觉得就是那个恶意软件传播的简化版。。。。