本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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++;\/\/桥数加一
}