Codeforces Round #254 (Div. 2) B. DZY Loves Chemistry (并查集)

时间:2022-05-13 02:56:13

题目链接

昨天晚上没有做出来,刚看题目的时候还把题意理解错了,当时想着以什么样的顺序倒,想着就饶进去了,

也被题目下面的示例分析给误导了。

题意:

有1-n种化学药剂  总共有m对试剂能反应,按不同的次序将1-n种试剂滴入试管,如果正在滴入的试剂能与已经滴入

的试剂反应,那么危险数*2,否则维持不变。问最后最大的危险系数是多少。

分析:其实这个题根本不用考虑倒入的顺序,只是分块就行,结果就是每个子集里元素的个数-1 和  的2的幂。

 #include <iostream>
#include <cstring>
#include <queue>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
const int maxn = + ;
int n, m, bin[maxn], f[maxn], cou;
int find(int x)
{
return bin[x]==x?x:(bin[x]=find(bin[x]));
}
void merge(int x, int y)
{
int fx = find(x);
int fy = find(y);
if(fx != fy)
{
bin[fx] = fy;
cou ++;
}
}
int main()
{
int i, x, y;
LL ans;
while(~scanf("%d%d", &n, &m))
{
cou = ;
for(i = ; i <= n; i++)
bin[i] = i;
while(m--)
{
cin>>x>>y;
merge(x, y);
}
ans = pow(, cou);
cout<<ans<<endl;
}
return ;
}