图中节点分配算法

问：

图中有节点 （1 ≤ ≤ 2⋅10^5） 和 （1 ≤ ≤ 2⋅10^5） 有向边。每个节点都有一个分配的数字（1 范围内的整数...），我们试图确定该数字。NNMMN

具有特定分配编号的所有节点都将具有指向指向具有另一个特定分配编号的其他节点的定向边。这也意味着，如果一个节点有多个有向边从它出来，那么它所指向的节点都具有相同的分配编号。我们必须使用此信息来确定数字的分配，以便最大化所有节点之间的非重复数字的数量。

由于有多个可能的答案，因此输出应按该顺序最小化分配给节点 1...的编号的赋值。从本质上讲，答案是词典上最小的一个。N

例：

在包含 9 个节点和 12 条边的图中，以下是边。对于两个整数和每行，有一个从 到 的有向边。ijij

3 4
6 9
4 2
2 9
8 3
7 1
3 5
5 8
1 2
4 6
8 7
9 4

正确的分配是节点 1、4、5 具有分配的编号;节点 2、6、8 具有分配的编号;节点 3、7、9 具有分配的编号。这是有道理的，因为节点 1、4、5 导致节点 2、6、8，节点 2、6、8 导致节点 3、7、9。123

为了解决这个问题，我认为您可以创建一个具有断开连接的子图的图，每个子图代表一组具有相同分配编号的节点。为此，我可以简单地扫描所有节点，如果一个节点有多个指向其他节点的有向边，则应将它们作为连接组件添加到图形中。如果某些节点已在图形中，则只需在当前组件之间添加边即可。

然后，对于其余节点，您可以找到它们已将边定向到哪些节点，并以某种方式使用该信息将它们添加到新图形中。

这个策略会奏效吗？如果是这样，我怎样才能正确实现算法的第二部分？

编辑1：早些时候我错误地解释了问题陈述;我现在已经发布了正确的解释和我解决问题的新方法。

编辑 2：因此，一旦我遍历了所有节点一次，按照我上面描述的方式添加边，我就会确定每个节点的组件。然后，我将再次遍历节点，这次确保以递归方式将其余边添加到图形中。例如，如果具有已分配编号的节点具有指向未分配编号的节点的定向边，则可以将该节点添加到其指定的组件中。我还可以使用 Union Find 来维护组件。

虽然这已经足够快了，但我担心可能会有错误 - 例如，当我执行此递归解决方案时，当为节点分配一个编号时，连接到该节点的具有分配编号的其他节点可能无法使用它。基本上，会有矛盾。我必须为此想出一个解决方案。