codeforces 156D Clues

题意

给定一个无向图，不保证联通。求添加最少的边使它联通的方案数。

题解

根据prufer序列，带标号无根树的方案数是\(n^{n-2}\)

依这个思想构建树即可。

代码

#include<bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define mp make_pair

#define pb push_back

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

#define sz(a) (int)a.size()

#define de(a) cout << #a << " = " << a << endl

#define dd(a) cout << #a << " = " << a << " "

#define all(a) a.begin(), a.end()

#define endl "\n"

typedef long long ll;

typedef pair<int, int> pii;

typedef vector<int> vi;

//---

const int N = 101010;

int n, m, p;

int pre[N], cnt[N];

int find(int x) {

	if(x == pre[x]) return x;

	return pre[x] = find(pre[x]);

}

void join(int x, int y) {

	x = find(x);

	y = find(y);

	pre[x] = y;

}

int main() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cin >> n >> m >> p;

	rep(i, 1, n+1) pre[i] = i;

	rep(i, 0, m) {

		int u, v;

		cin >> u >> v;

		join(u, v);

	}

	rep(i, 1, n+1) ++cnt[find(i)];

	ll ans = 1;

	int c = 0;

	rep(i, 1, n+1) if(cnt[i]) {

		ans = ans * cnt[i] % p;

		++c;

	}

	rep(i, 0, c-2) ans = ans * n % p;

	if(c == 1) ans = 1 % p;

	cout << ans << endl;

	return 0;

}