首页 > 代码库 > Codeforces Round #254 (Div. 2) B. DZY Loves Chemistry (并查集)
Codeforces Round #254 (Div. 2) B. DZY Loves Chemistry (并查集)
题目链接
昨天晚上没有做出来,刚看题目的时候还把题意理解错了,当时想着以什么样的顺序倒,想着就饶进去了,
也被题目下面的示例分析给误导了。
题意:
有1-n种化学药剂 总共有m对试剂能反应,按不同的次序将1-n种试剂滴入试管,如果正在滴入的试剂能与已经滴入
的试剂反应,那么危险数*2,否则维持不变。问最后最大的危险系数是多少。
分析:其实这个题根本不用考虑倒入的顺序,只是分块就行,结果就是每个子集里元素的个数-1 和 的2的幂。
1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 #include <cmath> 5 #include <cstdio> 6 #include <algorithm> 7 #define LL long long 8 using namespace std; 9 const int maxn = 50 + 10;10 int n, m, bin[maxn], f[maxn], cou;11 int find(int x)12 {13 return bin[x]==x?x:(bin[x]=find(bin[x]));14 }15 void merge(int x, int y)16 {17 int fx = find(x);18 int fy = find(y);19 if(fx != fy)20 {21 bin[fx] = fy;22 cou ++;23 }24 }25 int main()26 {27 int i, x, y;28 LL ans;29 while(~scanf("%d%d", &n, &m))30 {31 cou = 0;32 for(i = 1; i <= n; i++)33 bin[i] = i;34 while(m--)35 {36 cin>>x>>y;37 merge(x, y);38 }39 ans = pow(2, cou);40 cout<<ans<<endl;41 }42 return 0;43 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。