一个面经题

来源：13-6 拓扑排序

讲武德的年轻人

2022-08-09

bobo老师，想请教您一家公司的面经题。虽然我当时没有碰到这个题，但还是没有好的想法。

题目是这样的：有一个有向图，图中有N + 1个节点和N条路径。如果忽略方向，所有节点都连在一起。路径信息由两个数组给出，比如A = [1, 2, 3], B = [0, 0, 0]，表示有向图的边由A[i]指向B[i]。问题是，给定这样的数组A和B，能否找到一个结点，使得其他节点都可以到达该节点？如果有，返回该节点，如果没有，返回-1.

比如上边的例子A = [1, 2,3], B = [0, 0, 0]，返回0，因为0可以由其他所有节点（1, 2, 3）到达

例子二: A = [0, 1, 2, 4, 5], B = [2, 3, 3, 3, 2]，则应该返回节点2

例子三: A = [2, 3, 3, 4], B = [1, 1, 0, 0]，返回-1，没有节点满足条件。

我的第一个想法是利用leetcode 310 minimum height trees的思路，用拓扑排序解决。当从队列弹出的结点数量+留在队列中的结点数量等于所有节点数的时候，留在队列里的结点就是所求根节点。具体到这个题目，同样，当队列弹出的结点数量+留在队列中的结点数量等于所有节点数的时候，如果队列中只存在唯一节点，就是所求的所有节点可以到达的结点。如果队列中不唯一，说明队列中的两个结点不能相连，则说明没有，返回-1。这个思路可以解决上面三个测试用例。想请教您这个想法是否靠谱？谢谢！

写回答

1回答