답안 #19742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19742	2016-02-25T05:11:29 Z	xhae	트리 (kriii4_X)	C++14	0 / 100	0 ms	1216 KB

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;
	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

0.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1216 KB	Output is correct
2	Correct	0 ms	1216 KB	Output is correct
3	Correct	0 ms	1216 KB	Output is correct
4	Correct	0 ms	1216 KB	Output is correct
5	Correct	0 ms	1216 KB	Output is correct
6	Correct	0 ms	1216 KB	Output is correct
7	Correct	0 ms	1216 KB	Output is correct
8	Correct	0 ms	1216 KB	Output is correct
9	Incorrect	0 ms	1216 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 91.0

#	결과	실행 시간	메모리	Grader output
1	Halted	0 ms	0 KB	-