强连通分量 (有向图 无向图)

有向图

双连通分量图:max(p,q);
p 起点 q 终点

无向图

边双连通分量

判定: dfn[u] < low[to]
边双连通分量图: (cnt + 1) / 2;

点双连通分量

判定:
1:dfn[u] <= low[y]
2: (1) u 不是根节点 √
(2) u 是根节点 存在两个以上符合要求的yi

全部评论

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务