Submission #19853

#	Time	Username	Problem	Language	Result	Execution time	Memory
19853		tonyjjw	트리 (kriii4_X)	C++14	0 / 100	0 ms	4704 KiB

X

//*
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<vector>
#define all(A) (A).begin(), (A).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int MM = 200000;
const ll mod = 1000000007;

ll N;
int M;
int A[MM],B[MM];
int par[MM];
int cnt[MM];
int nN;

int getpar(int n){
	if(par[n]==n)return n;
	return par[n]=getpar(par[n]);
}

void merge(int a,int b){
	par[getpar(a)]=getpar(b);
}

ll mpow(ll a,ll p){
	ll r=1;
	while(p>0){
		if(p&1)r=r*a%mod;
		a=a*a%mod;
		p>>=1;
	}
	return r;
}

int main(){
	scanf("%lld%d",&N,&M);
	vector<int> nodes;
	for(int i=0;i<M;i++){
		scanf("%d%d",&A[i],&B[i]);
		nodes.push_back(A[i]),nodes.push_back(B[i]);
	}
	sort(all(nodes));
	nodes.resize(unique(all(nodes))-nodes.begin());
	for(int i=0;i<M;i++){
		A[i]=lower_bound(all(nodes),A[i])-nodes.begin();
		B[i]=lower_bound(all(nodes),B[i])-nodes.begin();
	}
	nN=nodes.size();
	for(int i=0;i<nN;i++)par[i]=i;
	for(int i=0;i<M;i++){
		merge(A[i],B[i]);
	}
	for(int i=0;i<nN;i++){
		cnt[getpar(i)]++;
	}
	ll ans=mpow(N,N-M-2);
	for(int i=0;i<nN;i++)if(par[i]==i){
		ans*=cnt[i];
		ans%=mod;
	}
	printf("%lld\n",ans);
	return 0;
}
//*/

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