NKOJP5682果老师炸桥

​

题目传送门 P5682果老师炸桥

思路

这道题是一道并查集；为什么？

因为在本题中，毁灭数对 $(i,j)$表示小岛 $i$ 和小岛 $j$ 不属于同一个连通块；此时，从小岛 $i$ 绝对无法走到小岛 $j$；而用 $tajian$ 算法没有必要，反正不是求割点；

但是，用并查集的方法， 会发现一个问题：并查集添边容易，删边难！因此，我们考虑从后往前枚举，每炸掉一个桥，就将这条边加入并查集，如果桥两端的点原先不在一个连通块中，就把这两个联通块间的元素个数相乘，算出去掉 $f(i,j)$ 后新增加的毁灭数对，将答案存储在数组中，最后倒序输出；

接下来大家可以自己尝试搓一下代码，实在不会的再往下看；

变量列表

• $nu{m}_i$ 答案数组
• $size{e}_i$ 存储第 $i$ 个小岛所在的连通块有多少个元素
• $fathe{r}_i$ 并查集的父亲数组
• $b{r}_i$ 存桥

AC Code

#include
#define int long long
using namespace std;
int n,m,num[100005],sizee[100005];
int father[100005],kkk=0;
struct lyt{
    int x;
    int y;
}br[100005]; 
int get(int x){
    if(father[x]==x){return x;}
    int fx=get(father[x]);
    father[x]=fx;
    return fx;
}
void onion(int x,int y){
    int fx=get(x); 
    int fy=get(y);
    father[fx]=fy;
    sizee[fy]+=sizee[fx];
    return;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        father[i]=i;
        sizee[i]=1;
    }
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&br[i].x,&br[i].y);
    }
    kkk=n*(n-1)/2;
    for(int i=m;i>=1;i--){
        int fx=get(br[i].x);
        int fy=get(br[i].y);
        num[i]=kkk;
        if(fx!=fy){
            kkk-=sizee[fx]*sizee[fy];
            onion(br[i].x,br[i].y);
        }
    }
    for(int i=1;i<=m;i++){
        printf("%lld\n",num[i]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

​