codeforces 445 B. DZY Loves Chemistry

2015年12月5日 0 作者 CrazyKK

http://codeforces.com/contest/445/problem/B

题意:一共有n种化学药品。m对关系,每对关系表示为x,y表示x和y相互反应。初始容器的danger值为1,当向容器中加入一个化学药品A,如果容器中存在化学药品和A反应,那么容器的danger值翻倍。否则不变。问一个最优的放置药品的顺序。

思路:容易发现。如果两个药品相互反应就连一条边。实际上这些药品构成了一个森林。而一个节点只要不是树的根节点,那么它在任何位置,对答案的贡献度都是*2.反过来说。所有的节点,只有根节点是对答案没有贡献的。那实际上,我们只需要dfs一遍,得到树的数目,用n减去树的数目,就是对答案有贡献的点的数目。

要注意开long long 。。。