Submission #19744

#	Time	Username	Problem	Language	Result	Execution time	Memory
19744		xdoju	트리 (kriii4_X)	C++14	0 / 100	0 ms	1212 KiB

X

#include <stdio.h>
#include <map>
#include <utility>
using namespace std;

const int MOD = 1000000007;

map<int, int> par;
map<int, int> cnt;

int getroot(int x){
  if(par.find(x) == par.end()) par[x] = x;
  if(par[x] == x) return x;

  return (par[x] = getroot(par[x]));
}

int mul(int x, int y){ return (long long)x * y % MOD; }

int power(int x, int y){
  if(y == 0) return 1;

  int r = power(x, y / 2);
  r = mul(r, r);
  if(y % 2 == 1) r = mul(r, x);
  return r;
}

int main(){
  int N, M; scanf("%d%d", &N, &M);

  bool val = true;

  for(int i = 1; i <= M; i++){
    int x, y; scanf("%d%d", &x, &y);

    int px = getroot(x), py = getroot(y);
    if(px == py) val = false;
    else par[px] = py;
  }

  if(!val){ puts("0"); }
  else{
    for(pair<int, int> pp : par){
      int x = pp.first;
      cnt[getroot(x)]++;
    }

    int NN = N - (int)par.size() + (int)cnt.size();

    int ans = 1;
    for(pair<int, int> pp : cnt) ans = mul(ans, pp.second);

    ans = mul(ans, power(N, NN - 2));

    printf("%d\n", ans);
  }
  return 0;
}

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