AcWing 4793. 危险程度
原题链接
困难
作者:
sonic407
,
2023-01-08 21:32:20
,
所有人可见
,
阅读 148
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, a[60];
int f(int x) {
return a[x] = a[x] == x ? a[x] : f(a[x]);
}
int u(int x, int y) {
a[f(x)] = f(y);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
a[i] = i;
}
for (int i = 1; i <= m; i ++ ) {
int x, y;
scanf("%d%d", &x, &y);
u(x, y);
}
int s[60] = {0};
for (int i = 1; i <= n; i++) {
s[f(i)] = 1;
}
int res = 0;
for (int i = 1; i <= n; i++ ) {
if (s[i] == 1) res ++ ;
}
long long d = 1;
for (int i = 1; i <= n - max(res, 1); i ++ ) {
d *= 2;
}
printf("%lld", d);
return 0;
}