---恢复内容开始---
Description
CC非常喜欢化学，并且特别喜欢把一大堆液体倒在一起。
现在CC有n种液体，其中m对会发生反应，现在她想把这n种液体按某种顺序倒入一个容器内，让她获得最刺激的体验，使危险系数尽量大。
我们可以这样计算危险系数，一开始容器内没有任何液体，危险系数为1。每次液体倒入容器时，若容器内已有一种或多种液体会与这种液体发生反应，则危险系数会乘2，否则危险系数不变。
请你求出把这n种液体倒在一起的最大危险系数。
Input Format
第一行为两个数n和m。
接下来m行，每行两个数a, b。表示a号液体和b号液体会发生反应。保证同一种边不重复出现。
30%的数据: \( 1 \le n \le 10 \)
100%的数据: \( 1 \le n \le 1000 \)
Output Format
一行，即最大危险系数。
Sample Input
3 2
1 2
2 3
Sample Output
4
数学上的本质是:
给定n个点,m个边,求出有多少个独立的连通块k
输出2^(n-k)
注意高精度........
对于这个问题, 可以想到先把每个点都当做一个独立的块,然后每输入一条边,我们就做出相应的更新 , 从而最后可以分成k个独立块
但是不能用图来存储,因为图的存储量太大,而且耗时.想到我们的目标只是要算出独立块的个数,可以利用集合的思想来完成这件事
这种数据结构叫做 并查集 Union Find
顾名思义有合并的过程 有查找的过程
理解的来源是:http://blog.csdn.net/dellaserss/article/details/7724401
这个博主简直太逗...
SJTU OJ的代码如下
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; int prenode[1050]; int num[350]={0}; int len = 1; //2次的power方 void mul2(int power){num[0]=1;for (int i = 0; i < power; ++i){int r = 0;int ori_len = len;for (int j = 0; j < ori_len ; ++j){int tmp = num[j]*2 + r;r = 0;num[j] = ( tmp ) % 10;// cout<<num[j]<<endl;if(tmp >= 10){r = (tmp)/10 ;//, num[len++]=r; }}if(r!=0)num[len++] = r;} }//查 int find(int x){//查找到x所在的子图的根节点 int res = x;while(res != prenode[res] ){//res是根节点的条件是 res的根节点是本身res = prenode[res];}//压缩路径 让此次查询中的所有涉及的节点的上级节点都是根节点 从而尽量形成只有二级的树结构(不能保证一定是 和输入的边顺序有关)while(x != res){int pre = prenode[x];prenode[x] = res;x = pre;}return res; } //并 void join(int x, int y){//把 x 和 y 并到同一子图中int rootx = find(x) , rooty = find(y);if(rootx != rooty)//x,y不属于同一子图时才有并的必要prenode[rootx] = rooty;//属于同一子图return; }int main(int argc, char const *argv[]) {int n,m; cin>>n>>m;//初始化n个点 根节点为自身 for (int i = 1; i <= n; ++i)prenode[i] = i; //调整每个边for (int i = 0; i < m; ++i){int x,y;cin>>x>>y;join(x,y); }//找连通区域的个数k int k = 0;for (int i = 1; i <= n; ++i) if(prenode[i]==i)k++;//cout<<k<<endl;//cout<<( 1<<(n-k) )<<endl;mul2(n-k);for (int i = len-1; i >=0; --i){cout<<num[i];}cout<<endl;return 0; }