初学缩点,关于重边
  • 板块学术版
  • 楼主lzy20091001
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/3/20 21:21
  • 上次更新2024/3/21 08:42:14
查看原帖
初学缩点,关于重边
932039
lzy20091001楼主2024/3/20 21:21
for (int i = 1; i <= n; i++)
    for (auto j : edge[i])
        if (graph[i].scc != graph[j].scc) // graph 是原图, scc 为这个结点的 scc 的编号
        {
            dag_edge[graph[i].scc].push_back(graph[j].scc); // dag_edge 为 DAG 的边
            dag[graph[j].scc].ind++; // 入度
        }

这样建 DAG 是否会导致重边?如果是,那么拓扑排序是否会出错?

2024/3/20 21:21
加载中...