海亮01/23图论专题

个人题单

T12

CF156D

题意

给定一个 \(n\) 个点 \(m\) 条边的带标号无向图，它有 \(k\) 个连通块，求添加 \(k-1\) 条边使得整个图连通的方案数，答案对 \(p\) 取模。

题解

没学过 \(Prüfer\) 序列 的自行学习。

不太会严谨证明

我们发现，如果将 \(k\) 个连通块缩成一个点，那么剩下 \(k\) 个孤立点（有标号），然后问你完全图 \(K_k\) 生成树有多少棵。

这个显然就是 \(Cayley\) 公式，有 \(n^{k-2}\) 种。

但是不太对，因为你没有确定每条边连接的是连通块中哪一个具体的点。

考虑用 \(Prüfer\) 序列重构树的过程，对于每一个序列，每一个点都需要拎出来连边，而这个连边的方案显然有 \(siz_u\) 个（设 \(siz_u\) 是连通块 \(u\) 的大小），然后发现每个连边都互不影响，然后你就赢了：P

最终答案是 \(n^{k-2}\prod siz_{u}\)。

这里需要注意，如果原来给定的图就是一整个连通块，那么方案数显然是 \(1\)，不过有一个点的 \(p=1\)，所以一定不要 \(puts("1")\) 要 \(1\mod p\) 啊（

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e5 + 10;
int n, m, mod;
int qpow(int x,int a){
    int res = 1;
    while(a){
        if(a & 1)res = (1ll * res * x) % mod;
        x = 1ll * x * x % mod;a >>= 1;
    }
    return res;
}

int fa[maxn], siz[maxn];
int getf(int x){return fa[x] == x ? x : fa[x] = getf(fa[x]);}

void main(){
    n = read(); m = read(); mod = read();
    if(n == 1){printf("%lld\n",1ll % mod);return;}
    for(int i = 1;i <= n;i++)fa[i] = i;
    for(int i = 1;i <= m;i++){
        int u = read(), v = read();
        if(getf(u) != getf(v))fa[getf(u)] = getf(v);
    }
    for(int i = 1;i <= n;i++){siz[getf(i)]++;}
    int ans = 1, cnt = 0;
    for(int i = 1;i <= n;i++){if(siz[i]){ans = (ans * siz[i]) % mod;cnt++;}}
    if(cnt == 1){printf("%lld\n",1ll % mod);return;}
    printf("%lld\n",ans * qpow(n,cnt - 2) % mod);
    return;
}
};
bool edmemory;
signed main(){
    auto stclock = clock();
    Call_me_Eric::main();
    auto edclock = clock();
    cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
    cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
    return 0;
}