题目描述
有 $n$ 种化学物质,编号 $1 \sim n$。
其中,有 $m$ 对物质之间会发生反应。
现在,要将这些化学物质逐个倒入同一个试管之中,具体倒入顺序不限。
我们需要计算一下试管的危险值。
已知,空试管的危险值为 $1$,每倒入一种化学物质,如果该物质能够与之前倒入试管中的一种或多种物质发生反应,则试管的危险值将乘以 $2$。
请你计算并输出,通过合理安排所有化学物质的倒入顺序,能够得到的试管的最大危险值。
输入格式
第一行包含两个整数 $n,m$。
接下来 $m$ 行,每行包含两个整数 $x,y$,表示化学物质 $x$ 和化学物质 $y$ 之间会发生反应。保证同一对化学物质在输入中最多出现一次。
输出格式
一个整数,表示最大危险值。
数据范围
前 $4$ 个测试点满足 $1 \le n \le 10$。
所有测试点满足 $1 \le n \le 50$,$0 \le m \le \frac{n(n-1)}{2}$,$1 \le x < y \le n$。
输入样例1:
1 0
输出样例1:
1
输入样例2:
2 1
1 2
输出样例2:
2
输入样例3:
3 2
1 2
2 3
输出样例3:
4
采用并查集来做
当一个试管中加入1,不爆炸
加入1和2 发生爆炸
1和2反应后生成一种新物质 此时在加入3 发生爆炸
一共发生两次爆炸
因此当合并集合后如果这个数跟之前不属于同一个集合(也就是生成了新的物质,发生了一次爆炸),此时res * 2;
#include "bits/stdc++.h"
using namespace std;
const int N = 60;
int p[N];
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
p[i] = i;
}
while (m --) {
int a, b;
cin >> a >> b;
p[find(a)] = find(b);
}
long long res = 1;
for (int i = 1; i <= n; i++) {
if (i != p[i]) {
res *= 2;
}
}
cout << res << '\n';
return 0;
}