小 X 的液体混合

小 X 的液体混合

虽然小 X 不喜欢化学原理,但他特别喜欢把一大堆液体倒在一起。
现在小 X 有 n 种液体,其中 m 对会发生反应。现在他想把这 n 种液体按某种顺序倒入一个容器
内,让他获得最刺激的体验,也就是使危险系数尽量大。
我们可以这样计算危险系数,一开始容器内没有任何液体,危险系数为 1。每次液体倒入容器时,
若容器内已有一种或多种液体会与这种液体发生反应,则危险系数会乘 2,否则危险系数不变。
最大危险系数小 X 不会算,希望你帮帮他。

Input

第一行包含两个整数 n, m。
接下来 m 行,每行包含两个整数 a, b,表示液体 a 和液体 b 会发生反应。

Output

第一行包含一个整数,表示最大危险系数。

思路

首先我们可以知道:
每 一 个 连 通 块 一 定 有 一 个 液 体 倒 入 时 无 法 增 加 危 险 系 数 每一个连通块一定有一个液体倒入时无法增加危险系数 每一个连通块一定有一个液体倒入时无法增加危险系数
证明:
在每一个连通块中,连通的边都是双向的,而且每2个点之间都能相连(这不是废话吗),所以我们可以删去一部分不必要的边,组成一颗树,而这颗树的根在进入瓶子时是无法增加危险系数的,而当根进入后,让它的子节点进入都可以增加,再让子节点的子节点进去,让子节点的子节点进入……
那么如何统计连通块的个数呢?
由于每2个点之间都能相连,所以我们可以让任何一个点做根,用并查集统计就可以了
记住之后累乘写高精


code:

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
bool a[1001][1001];
int f[1001];
char x2[100001];
string chen(string x)
{
 for (int i=x.size()-1,j=1;i>=0;i--,j++) x2[j]=x[i]-'0';
 int p=0;
 for (int i=1;i<=x.size();i++)
 {
  int t=x2[i]*2+p;
  p=t/10;
  x2[i]=t%10;
 }
 x2[x.size()+1]=p;
 string s="";
 int i=100000;
 while (i>1&&x2[i]==0) i--;
 while (i>=1)
 {
  char xx=x2[i]+'0';
  s+=xx;
  i--;
 }
 return s;
}//高精度乘法(乘2)
int find(int x)
{
 if (x==f[x]) return x;
 return f[x]=find(f[x]);
}//并查集路径压缩
int main()
{
 int n,m;
 cin>>n>>m;
 for (int i=1;i<=n;i++) f[i]=i;
 for (int i=0;i<m;i++)
 {
  int x,y;
  cin>>x>>y;
  f[find(y)]=find(x);
 }
 string s="";
 char x='1';
 s+=x;
 int tot=n;
 for (int i=1;i<=n;i++)
 {
  if (find(i)==i) tot--;
 }//求连通块个数(根的个数)
 for (int i=1;i<=tot;i++)
 {
  s=chen(s);
 }
 for (int i=0;i<s.size();i++)
 {
  int u=s[i];
  cout<<u-'0';
 }return 0;
}
栏目
728_90 cn stocks