codeforces 445 B. DZY Loves Chemistry
http://codeforces.com/contest/445/problem/B
题意：一共有n种化学药品。m对关系，每对关系表示为x,y表示x和y相互反应。初始容器的danger值为1，当向容器中加入一个化学药品A,如果容器中存在化学药品和A反应，那么容器的danger值翻倍。否则不变。问一个最优的放置药品的顺序。
思路：容易发现。如果两个药品相互反应就连一条边。实际上这些药品构成了一个森林。而一个节点只要不是树的根节点，那么它在任何位置，对答案的贡献度都是*2.反过来说。所有的节点，只有根节点是对答案没有贡献的。那实际上，我们只需要dfs一遍，得到树的数目，用n减去树的数目，就是对答案有贡献的点的数目。
要注意开long long 。。。
/* ***********************************************
Author :111qqz
Created Time :2015年12月05日 星期六 17时13分51秒
File Name :code/cf/problem/445/B.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19using namespace std;
20const double eps = 1E-8;
21const int dx4[4]={1,0,0,-1};
22const int dy4[4]={0,-1,1,0};
23const int inf = 0x3f3f3f3f;
24const int N=55;
25bool vis[N];
26int n,m;
27vector<int>edge[N];
28LL ans;
29LL tree_num;
30void dfs( int cur)
31{
1 vis[cur] = true;
2 for ( int i = 0 ; i < edge[cur].size(); i++)
3 {
4 int v = edge[cur][i];
5 if (!vis[v])
6 {
7 dfs(v);
8 }
9 }
10}
11int main()
12{
13 #ifndef ONLINE_JUDGE
14 freopen("code/in.txt","r",stdin);
15 #endif
1 scanf("%d %d",&n,&m);
2 ms(vis,false);
3 for ( int i = 0 ; i < m ; i++)
4 {
5 int u,v;
6 scanf("%d %d",&u,&v);
7 edge[u].push_back(v);
8 edge[v].push_back(u);
9 }
10 tree_num = 0 ;
11 for ( int i = 1 ; i <= n ; i++)
12 {
13 if (!vis[i])
14 {
15 dfs(i);
16 tree_num++;
17 }
18 }
19 ans = 1;
20 ans = (LL)(1)<<(LL(n-tree_num));
21 cout<<ans<<endl;
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}