zcmimi's blog

arrow_back强连通分量共2篇文章

avatar
zc
2020-04-01 19:37:00
查看原题

点击跳转

经典的link-cut tree维护连通分量

首先看到这种题我们可以考虑倒序添加

假设每个点代表一个双连通分量,那么两个点之间的关键路径数就是链长-1

可以用LCT+并查集来维护

连接一条边:

  1. 两端在同一个双连通分量中: 什么都不用干

  2. 两端还未连通: 直接link

  3. 两端已经联通: 缩点

    将连接两端的路径提取出来,合并这些点

avatar
zc
2019-12-31 22:54:00
查看原题

点击跳转

夫妻之间:girl \to boy

情人之间:boy \to girl

Tarjan求强连通分量,对于一对夫妻,如果两人在同一个强连通分量里,那么这对婚姻就是不安全的,反之,则是安全的。

1/1
Search
search