Submission #20037

#	Time	Username	Problem	Language	Result	Execution time	Memory
20037		sys7961	트리 (kriii4_X)	C++14	0 / 100	0 ms	3556 KiB

X

#include <cstdio>
#include <vector>
#include <set>
#include <map>
#define ll long long
const ll M = 1000000007;
struct line{
	ll n1, n2, p;
};
line lines[100001];
std::map<ll, line *> list;
ll find(ll i) {
	if (i == lines[i].p) return i;
	else {
		lines[i].p = find(lines[i].p);
		return lines[i].p;
	}
}
ll merge(ll i, ll j) {
	ll f1 = find(i), f2 = find(j);
	if (f1 == f2) return 0;
	lines[f1].p = lines[f2].p;
	return 0;
}
ll pow1(ll n, ll b) {
	if (b == 0) {
		return 1;
	}
	ll temp = pow1(n % M, b / 2) % M;
	if (b % 2 == 1) {
		return temp*temp%M*(n%M) % M;
	}
	return temp*temp%M;
}
int main(void) {
	ll n, k;
	scanf("%lld%lld", &n, &k);
	for (ll i = 0; i < k; i++) {
		lines[i].p = i;
		scanf("%lld %lld", &lines[i].n1, &lines[i].n2);
		auto f1 = list.find(lines[i].n1);
		auto f2 = list.find(lines[i].n2);
		if (f1 != list.end()) 
			merge(i, f1->second->p);
		else
		{
			list.insert({ lines[i].n1, &lines[i] });
			n--;
		}
		
		if (f2 != list.end()) 
			merge(i, f2->second->p);
		else
		{
			list.insert({ lines[i].n2, &lines[i] });
			n--;
		}
	}
	std::set<ll> tot;
	for (ll i = 0; i < k; i++) {
		tot.insert(find(lines[i].p));
	}
	n += tot.size();
	printf("%lld", pow1(2, n) % M);
}

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