| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 20085 |
2016-02-25T10:46:55 Z |
hongjun7 |
트리 (kriii4_X) |
C++14 |
|
0 ms |
1212 KB |
#include <stdio.h>
#include <map>
using namespace std;
const int mod = 1e9+7;
int N, M;
map<int, int> par, cnt;
int F(int x) {
if (!par.count(x)) par[x] = x;
if (par[x] == x) return x;
return (par[x] = F(par[x]));
}
int mul(int x, int y) { return (long long)x * y % mod; }
int fm(int x, int y) {
if (y <= 0) return 1;
int r = fm(x, y / 2);
r = mul(r, r);
if (y % 2 == 1) r = mul(r, x);
return r;
}
int main() {
scanf("%d%d", &N, &M);
bool ok = 1;
for (int i = 1; i <= M; i++) {
int x, y; scanf("%d%d", &x, &y);
int px = F(x), py = F(y);
if (px == py) ok = 0;
else par[px] = py;
}
int res = 0;
if (ok) {
for (auto x : par) cnt[F(x.first)]++;
res = fm(N, N - par.size() + cnt.size() - 2);
for (auto x : cnt) res = mul(res, x.second);
}
printf("%d", res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1212 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
1212 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
