Submission #19746

#	Time	Username	Problem	Language	Result	Execution time	Memory
19746		xhae	트리 (kriii4_X)	C++14	9 / 100	1000 ms	16264 KiB

X

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

using namespace std;

const int mod = 1000000007;
map<int,int> groups;
map<int, 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) {
	if (!groups.count(a)) {
		groups[a] = a;
		groupsize[a] = 1;
	}
	if (!groups.count(b)) {
		groups[b] = b;
		groupsize[b] = 1;
	}
	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;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	long long ans = 1;
	for (int i = 0; i < m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--, b--;
		if (!group_merge(a, b)) {
			ans = 0;
		}
	}
	if (m >= n)
		ans = 0;
	int c = n - m;
	if (c >= 2) {
		for (int i = 0; i < c - 2; i++) {
			ans *= n;
			ans %= mod;
		}
		for (auto kv : groups) {
			if (kv.first == kv.second) {
				ans *= groupsize[kv.first];
				ans %= mod;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

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