有向图中特征传播的高效算法咨询：是否存在快于O(n²)的方案？

核心思路是先把图中的强连通分量（SCC）合并成单个节点，将原图转化为有向无环图（DAG），再通过拓扑排序高效传递颜色信息，彻底避免O(n²)级别的重复遍历。

1. 颜色的位掩码表示 #

把红、绿、蓝三种颜色用位掩码编码，将颜色叠加转化为高效的位运算：

• 红 = 1（二进制001）
• 绿 = 2（二进制010）
• 蓝 = 4（二进制100）
• 无颜色 = 0
  颜色叠加直接用按位或操作（|），比如红+绿=3（001 | 010 = 011），O(1)即可完成，完全适配百万级节点的处理速度。

2. 提取强连通分量（SCC） #

用Tarjan或Kosaraju算法遍历原图，找出所有SCC：

• 同一个SCC内的节点互相可达，因此整个分量的颜色是内部所有节点颜色的按位或结果（分量内任意节点的颜色都要传递给其他所有节点）。
• 这一步时间复杂度为O(n + m)，完全支撑百万级节点的规模。

3. 构建缩点后的DAG #

把每个SCC当作一个新节点：

• 遍历原图的所有边，如果边的起点属于SCC A，终点属于SCC B且A≠B，则在DAG中添加一条A→B的边（注意去重，避免同一条边重复添加）。
• 最终得到的DAG无环，后续处理逻辑会更简洁高效。

4. 拓扑排序DAG #

对缩点后的DAG进行拓扑排序，得到一个节点顺序，保证所有前驱节点排在后继节点之前。这一步时间复杂度为O(n' + m')，其中n'是SCC数量，m'是DAG的边数，远小于原图的n和m。

5. 按拓扑顺序传递颜色 #

• 初始化每个缩点的颜色为步骤2中计算的分量总颜色。
• 按拓扑顺序遍历每个缩点u：
  • 对u的每个邻居v（DAG中的边u→v），执行v.color = v.color | u.color——因为u能到达v，所以v要继承u的所有颜色。
  • 由于拓扑顺序保证u在v之前处理，当处理v时，它已经累积了所有能到达它的前驱缩点的颜色，再传递给v的邻居即可完成全量颜色继承。

6. 还原到原节点 #

每个原节点的最终颜色就是它所属SCC的最终颜色——SCC内部互相可达，且所有能到达该SCC的其他分量的颜色已经通过DAG传递完成。

为什么这比O(n²)高效？ #

• 原图中的环被合并成单个SCC，避免了反复遍历环内节点的冗余操作。
• DAG的拓扑排序只处理每个边一次，没有重复的DFS遍历，整体时间复杂度是线性的O(n + m)，对于百万级节点的图（只要边数不是极端稠密）完全可行。

注意事项 #

• 若原图是极端稠密图（m接近n²），任何算法都无法避免O(n²)的时间，但这种场景在百万级节点的实际应用中极少出现（内存也无法承载如此多的边）。
• 位掩码的使用是性能关键，把颜色叠加从集合操作转化为整数位运算，极大提升了处理速度，完美适配大规模数据场景。

内容的提问来源于stack exchange，提问作者Torn