首页 > 代码库 > 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 }