CF156D Clues （prufer序列+计数）

DrBit · 2021-04-06 23:20:39 · 个人记录

题面

题解

实在是不想打公式。

#include<iostream>//test3
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN = 1e5 + 50;
int N, M, mod, ans = 1;
int fa[MAXN], siz[MAXN];
int finda(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = finda(fa[x]);
}
void link(int x, int y)
{
    int fx = finda(x);
    int fy = finda(y);
    fa[fx] = fy;
}
int pown(int x, int p)
{
    int t = 1, w = x;
    while (p)
    {
        if (p & 1)
            t = t * w % mod;
        w = w * w % mod;
        p >>= 1;
    }
    return t;
}
signed main()
{
    scanf("%lld%lld%lld", &N, &M, &mod);
    for (int i = 1; i <= N; ++i)
        fa[i] = i;
    for (int i = 1; i <= M; ++i)
    {
        int u, v;
        scanf("%lld%lld", &u, &v);
        link(u, v);
    }
    for (int i = 1; i <= N; ++i)
    {
        int fx = finda(i);
        siz[fx]++;
    }
    int k = 0;
    for (int i = 1; i <= N; ++i)
    {
        if (i != finda(i))
            continue;
        ans = ans * siz[i] % mod;
        k++;
    }
    if (k >= 2)
        ans = ans * pown(N, k - 2) % mod;
    else
        ans = 1 % mod;
    printf("%lld\n", ans);
    return 0;
}