CF 156D Clues

题目描述

https://codeforces.com/problemset/problem/156/D

简要题意：给定一个 $n$ 个点 $m$ 条边的简单无向图，如果原图有 $k$ 个连通块，求添加 $k-1$ 条边是整个图连通的方案数

$n,m\le 10^5$

Solution

我们令 $d_i$ 表示第 $i$ 个连通块的度数，$s_i$ 表示第 $i$ 个连通块的大小，那么我们有

$$\begin{aligned} ans&=\sum_{i\in[1,k],d_i\in[1,k-1],\sum_{i=1}^k(d_i-1)=k-2}\binom{k-2}{d_1-1,d_2-1,\cdots,d_k-1}\prod_{i=1}^ks_i^{d_i} \end{aligned}$$

这个式子大概就是我们枚举每个连通块的度数，然后根据 $prufer$ 序列来计数，后面那个 $\prod$ 是因为每个连通块向外连边有 $s_i$ 种选择

这个式子我们利用多项式定理来可以得到 $ans=n^{k-2}\prod_{i=1}^ks_i$

#include <iostream>
#include <cstring>
#include <algorithm>
#define ll long long
#define maxn 100010
using namespace std;

int p;
ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

int n, m;

int fa[maxn], sz[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return ;
    fa[fx] = fy; sz[fy] += sz[fx];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> p; init_fa(n); 
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        merge(x, y); 
    } int k = 0; ll t = 1; 
    for (int i = 1; i <= n; ++i) if (find(i) == i) ++k, t = t * sz[i] % p;
    if (k == 1) cout << 1 % p << "\n";
    else cout << pow_mod(n, k - 2) * t % p << "\n";
    return 0;
}