Submission #19995

#	Time	Username	Problem	Language	Result	Execution time	Memory
19995		gs12117	트리 (kriii4_X)	C++98	100 / 100	195 ms	11084 KiB

X

#include<stdio.h>
#include<map>
long long int n,m;
int mod=1000000007;
long long int ans;
std::map<int,int> mp;
int eg[100100][2];
int cnt;
int uft[200100];
int uftn[200100];
int mpow(int x,int y){
	if(y==0)return 1;
	long long int r=mpow(x,y/2);
	r*=r;
	r%=mod;
	if(y%2==1){
		r*=x;
		r%=mod;
	}
	return r;
}
int uftf(int x){
	if(x==uft[x])return x;
	return uft[x]=uftf(uft[x]);
}
int main(){
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d%d",&eg[i][0],&eg[i][1]);
		if(mp[eg[i][0]]==0){
			cnt++;
			mp[eg[i][0]]=cnt;
		}
		eg[i][0]=mp[eg[i][0]];
		if(mp[eg[i][1]]==0){
			cnt++;
			mp[eg[i][1]]=cnt;
		}
		eg[i][1]=mp[eg[i][1]];
	}
	for(i=1;i<=cnt;i++){
		uft[i]=i;
		uftn[i]=1;
	}
	for(i=0;i<m;i++){
		if(uftf(eg[i][0])!=uftf(eg[i][1])){
			uftn[uftf(eg[i][0])]+=uftn[uftf(eg[i][1])];
			uft[uftf(eg[i][1])]=uftf(eg[i][0]);
		}
		else{
			printf("0");
			return 0;
		}
	}
	ans=1;
	for(i=1;i<=cnt;i++){
		if(uftf(i)==i){
			ans*=uftn[i];
			ans%=mod;
		}
	}
	if(m==n-1)ans=1;
	else ans*=mpow(n,n-m-2);
	ans%=mod;
	printf("%lld",ans);
}

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