menu zcmimi's blog

arrow_back 强连通分量

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

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

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

可以用LCT+并查集来维护

连接

zc
2020-04-01 19:37

夫妻之间:girl \to boy

情人之间:boy \to girl

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

zc
2019-12-31 22:54
1 / 1
Search
search