ABC075C Bridge 题解

__S08577__ · 2024-03-02 15:30:48 · 题解

一开始看到这道题的时候，就想到用tarjan，求桥数。 但是我想到了用并查集来求（hb说可以用并查集做，当然选简单的）。 我们枚举每一个边 i，设这条边 i 为断点，再枚举 j（j \ne i)，将 x_j 和 y_j 联通。第一个循环最后，判断 x_i 和 y_i 是否在一个集合里。

部分代码

for(int i=1;i<=m;i++){
    init();//并查集初始化
    for(int j=1;j<=m;j++) if(j!=i) fa[findf(x[j])]=findf(y[j]);
    if(findf(x[i])!=findf(y[i])) cnt++;//桥数加一
}