题目描述
看题大概可以知道 n个点可以分成m个连通块
所以我们可以贪心的一个个连通块的放,并且得出一定是最优解,
因为每个连通块放下的时候,除了第一个其他都对答案有贡献
所以我们可以知道每个连通的对答案的贡献应该是 size【i】- 1(因为要先放一个才能保证后面每一个都和瓶子里面的有关系)
所以总的答案的贡献应该是 m = n - 连通块的数量
那么答案应该是 pow(2,m-1)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int p[N],num[N];
int n,m;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int x,int y){
int a = find(x),b = find(y);
if(a == b) return ;
p[a] = b;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) p[i] = i;
while(m--)
{
int x,y;
cin >> x >> y;
merge(x,y);
}
long long res = 1;
for(int i = 1; i <= n; i++)
if(p[i] != i)
res <<= 1;
cout << res;
}