Submission #19742

# Submission time Handle Problem Language Result Execution time Memory
19742 2016-02-25T05:11:29 Z xhae 트리 (kriii4_X) C++14
0 / 100
0 ms 1216 KB
#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;
}
# Verdict Execution time Memory 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 -
# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -