Submission #19760

#	Time	Username	Problem	Language	Result	Execution time	Memory
19760		xhae	트리 (kriii4_X)	C++14	9 / 100	1000 ms	6316 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;
}

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);
	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) {
		for (int i = 0; i < c - 2; i++) {
			ans *= n;
			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: 0 / 91