题目链接:Codeforces 445B DZY Loves Chemistry
题目大意:有若干种化学药品,给出两两会反应的关系,现在要将药物依次放入一个容器中,容器中的化学药品可以互相反应,如果当前放入的药品能与已经在容器中的某一药品反应,那么危险值翻倍,即*2,初始值为1,求一顺序,使得为危险值最大。
解题思路:并查集求最小联通分量s,2n−s即为答案。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 50;
typedef long long ll;
int n, m, f[maxn+5];
int getfar(int x) {
return x == f[x] ? x : f[x] = getfar(f[x]);
}
ll power (ll x, int t) {
ll ans = 1;
while (t) {
if (t&1)
ans = ans * x;
x = x * x;
t /= 2;
}
return ans;
}
int main () {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++)
f[i] = i;
int c = n, a, b;
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
int fa = getfar(a);
int fb = getfar(b);
if (fa != fb) {
f[fa] = fb;
c--;
}
}
printf("%lld\n", power(2LL, n-c));
return 0;
}
分享到:
相关推荐
【并查集】Codeforces 566D Restructuring Company题面在这里对于本题,只需要再维护一个并查集表示i所在联通块的最右位置因为相邻
Codeforces - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
# sublime-plugin-for-codeforces 自定义构建,用于从 codeforces 获取测试用例并检查程序是否正确。 平台:GNU/Linux 语言:Python2.7.9 描述:这个程序从 codeforces 中获取测试用例,并告诉你程序的输出是否与...
Codeforces round 678 D2_Codeforces_源码
并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,只需要找度为222的点即可 如果一条边两个顶点的度都为222,我们可以用并查集判断两点是否在一个子图里 用并查集判断两...
打codeforces的神器
codeforces-js Codeforces JS
使用 C# + WPF 开发 --- 还在发愁打了那么多场比赛都没有进入首页么? 还在为了前 5 的 hacker 名额阅读千份代码么? 是的,你没有看错! 这是一个 Edu & Div.3 轮 Open hacking 错误代码自动查找器!...