Submission #19887

#	Time	Username	Problem	Language	Result	Execution time	Memory
19887		gs13068	트리 (kriii4_X)	C++98	100 / 100	640 ms	16260 KiB

X

#include <cstdio>
#include <map>

const int p = 1000000007;

using namespace std;

int pw(int x, int y)
{
	return y & 1 ? (long long)pw(x, y ^ 1)*x%p : y ? pw((long long)x*x%p, y >> 1) : 1;
}

map<int, int> M, S;

int f(int x)
{
	if (M.find(x) == M.end()) M[x] = x;
	int t = M[x];
	return x == t ? x : M[x] = f(t);
}

void g(int x, int y)
{
	x = f(x);
	y = f(y);
	if (S.find(x) == S.end()) S[x] = 1;
	if (S.find(y) == S.end()) S[y] = 1;
	S[x] += S[y];
	M[y] = M[x];
}

int main()
{
	map<int, int>::iterator it;
	int i, j, k, n, m, r;
	scanf("%d%d", &n, &m);
	for (k = 0; k < m;k++)
	{
		scanf("%d%d", &i, &j);
		if (f(i) == f(j))
		{
			puts("0");
			return 0;
		}
		g(i, j);
	}
	if (m == n - 1)
	{
		puts("1");
		return 0;
	}
	r = pw(n, n - m - 2);
	for (it = S.begin(); it != S.end(); it++) if (it->first == f(it->first)) r = (long long)r * it->second % p;
	printf("%d", r);
}

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