CodeForces - 156D：Clues（矩阵树定理&并查集）

题意：给定N点，M边，求添加最少的边使之变为连通图的方案数。

思路：注意题目给出的M边可能带环，即最后生成的不一定是一棵树。但是影响不大。根据矩阵树定理，我们知道生成树的数量=N^(N-2)，即点数^(连通数-2)。

此题把已经连通的看成一个整体，就可以得到数量为N^(cnt-2)，然后考虑连通块内部的点，因为内部贡献的时候每个点都有相同的机会，所以乘内部点的个数。

注意只有一个连通块时（已经连通的情况）不乘法个数。

（只会套公式，证明我不知道啊。。。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define ll long long

using namespace std;

const int maxn=;

int N,M,P,fa[maxn],num[maxn],cnt; ll ans;

int find(int u){

    if(u==fa[u]) return fa[u];

    return fa[u]=find(fa[u]);

}

int main()

{

    scanf("%d%d%d",&N,&M,&P);

    rep(i,,N) fa[i]=i;

    rep(i,,M){

        int u,v; scanf("%d%d",&u,&v);

        int f1=find(u),f2=find(v);

        if(f1!=f2) fa[f1]=f2;

    }

    rep(i,,N) num[find(i)]++; ans=;

    rep(i,,N) if(num[i]) cnt++,ans=ans*num[i]%P;

    rep(i,,cnt-) ans=ans*N%P;

    if(cnt==) ans=;

    printf("%I64d\n",ans%P);

    return ;

}