Submission #19934

#	Time	Username	Problem	Language	Result	Execution time	Memory
19934		Namnamseo	트리 (kriii4_X)	C++14	100 / 100	149 ms	10496 KiB

X

#include <cstdio>
#include <map>
using namespace std;
map<int,int> vv;
int par [200010], vind;
int size[200010];
bool chk[200010];
int n,m;
inline int conv(int x){
    int& ret=vv[x];
    if(ret==0){
        ++vind;
        par [vind]=vind;
        size[vind]=1;
        ret =vind;
    }
    return ret;
}
int root(int x){ return (x==par[x])?x:(par[x]=root(par[x])); }
const int M=int(1e9)+7;
long long pow(long long x,long long y){
    if(y==0)return 1;
    if(y==1)return x;
    long long o=pow(x,y/2);
    if(y%2==0)return o*o%M;
    else return o*o%M*x%M;
}
int main()
{
    scanf("%d%d",&n,&m);
    int i,a,b;
    for(i=0;i<m;++i){
        scanf("%d%d",&a,&b);
        a=root(conv(a)); b=root(conv(b));
        if(a==b){
            puts("0"); return 0;
        }
        par [a]=b;
        size[b]+=size[a];
    }
    int allmul=1;
    for(i=1; i<=vind; ++i){
        a=root(i);
        if(chk[a]) continue;
        chk[a]=true;
        allmul=(allmul*1LL*size[a])%M;
    }
    if(n==m+1){
        printf("%d\n",1);
    } else
        printf("%d\n",int( pow(n, n-m-2) * allmul % M ));
    return 0;
}

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