放一道算法题:
给一个 DAG,每个节点都带有一个整数值。对节点进行拓扑排序,称一个拓扑排序是合法的,当且仅当在拓扑排序后,每个节点排在序列中的位置(即节点在拓扑排序中的下标)都不大于节点上的值。
要求分别对 DAG 中的每个节点,计算在所有合法的拓扑排序中,这个节点能被排到的最靠前的位置是多少。
咋做啊.jpg
给一个 DAG,每个节点都带有一个整数值。对节点进行拓扑排序,称一个拓扑排序是合法的,当且仅当在拓扑排序后,每个节点排在序列中的位置(即节点在拓扑排序中的下标)都不大于节点上的值。
要求分别对 DAG 中的每个节点,计算在所有合法的拓扑排序中,这个节点能被排到的最靠前的位置是多少。
咋做啊.jpg