Submission #19770

#	Time	Username	Problem	Language	Result	Execution time	Memory
19770		xhae	트리 (kriii4_X)	C++14	100 / 100	99 ms	5028 KiB

X

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int mod = 1000000007;
vector<int> groups;
vector<int> groupsize;

int get_root(int a) {
	int t = a;
	while (a != groups[a])
		a = groups[a];
	while (t != groups[t])
	{
		int p = groups[t];
		groups[t] = a;
		t = p;
	}
	return a;
}

bool group_merge(int a, int b) {
	a = get_root(a);
	b = get_root(b);
	if (a == b)
		return false;
	if (groupsize[a] < groupsize[b]) {
		swap(a, b);
	}
	groups[b] = a;
	groupsize[a] += groupsize[b];
	return true;
}

long long modpow(long long a, long long p, long long m)
{
	long long r = 1;
	while (p) {
		if (p & 1)
		{
			r = (r*a) % m;
		}
		a = (a*a) % m;
		p >>= 1;
	}
	return r;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	long long ans = 1;

	vector<pair<int, int>> dat;
	vector<int> vertices;
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--, b--;
		dat.emplace_back(a, b);
		vertices.push_back(a);
		vertices.push_back(b);
	}
	sort(vertices.begin(), vertices.end());
	vertices.erase(unique(vertices.begin(), vertices.end()), vertices.end());
	groupsize.assign(vertices.size(), 1);
	groups.reserve(vertices.size());
	for (int i = 0; i < vertices.size(); i++) {
		groups.push_back(i);
	}
	for (int i = 0; i < m; i++) {
		int a = dat[i].first;
		int b = dat[i].second;
		a = lower_bound(vertices.begin(), vertices.end(), a) - vertices.begin();
		b = lower_bound(vertices.begin(), vertices.end(), b) - vertices.begin();
		if (!group_merge(a, b)) {
			ans = 0;
		}
	}
	if (m >= n)
		ans = 0;
	int c = n - m;
	if (c >= 2) {
		ans *= modpow(n, c-2, mod);
		ans %= mod;
		for (int i = 0; i < vertices.size(); i++) {
			if (i == groups[i]) {
				ans *= groupsize[i];
				ans %= mod;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 91 / 91