第三章 图论 No.9有向图的强连通与半连通分量

发布网友 发布时间：2024-11-08 04:35

我来回答

共1个回答

热心网友 时间：2024-11-08 05:08

连通分量是无向图的概念，强调强连通分量是一些点的集合，如果加入其他点，则该集合中的任意两点就不能互相递达。半连通分量则允许从任两点中仅有一个路径可达。

应用实例：通过使用缩点技术，将所有强连通分量简化为一个点，可以将有向图转换为有向无环图（DAG），从而利用拓扑排序解决最短路径问题。

强连通分量简称scc，判断当前点是否在scc中，关键在于该点最终会到达已遍历过的祖先节点。点可能存在自环，理论上它仍被视为强连通分量，尽管书上可能对此有不同描述。

Tarjan算法通过定义两个时间戳：dfs[u]表示遍历到u的时间，low[u]表示从u开始走，能遍历到的最小时间戳。若u是强连通分量的最高点，那么dfn[u] == low[u]，意味着该点无法再往上走到其他点。

缩点实现：遍历所有点及其邻点，若两点不在同一强连通分量中，则在两点之间添加边。强连通分量编号的顺序即为拓扑序，可通过bfs或dfs求得。首先遍历所有点，从入边为0的点开始dfs，将该点编号加入序列中，序列的逆序即为拓扑序。

1174. 受欢迎的牛：通过反向建图，使用bfs判断当前点是否能递达其他所有点。如果图中存在多个入边为0的点，选择其一进行dfs，之后在拓扑序开头加上这几个入边为0的点。若图中出边为0的点的数量为1，说明该点是受欢迎的，统计环中节点的数量即可。

367. 学校网络：缩点后，图中入度为0的点为第一问的答案。第二问要求加入的边数，结论为：图有P个入度为0的点，Q个出度为0的点，需要加max(P, Q)个点。缩点后的图中，从起点到终点的路径即为答案。

1175. 最大半连通子图：找出所有强连通分量，使用Tarjan算法缩点，得到有向无环图。找出极大半连通分量，按照拓扑序递推，计算最长路径。注意点数不同才算不同的半连通子图，且边的权重是分量中的点数，不需要考虑重边。

368. 银河：转换为差分约束问题，使用最短路算法求解。首先构建虚拟源点与所有点的边，从虚拟源点开始spfa求最长路。判断负环，得到最小值。

调试：注意缩点后图的入度和出度，确保正确判断。拓扑序递推时，要记录点的数量和路径数量，避免重复计算。使用快速的数据结构，如unordered_set，优化性能。