并查集

畅通工程

某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时，输入结束，该用例不被处理。

Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。

思路
对于N个城镇最多需要N-1条路，每次合并时道路数量减一

AC代码

#include <bits/stdc++.h>

using namespace std;

int pre[1005];

int find(int x){
    if (x==pre[x]) return pre[x];
    else return find(pre[x]);
}

void un(int a,int b){
    pre[find(a)]=find(b);
}

int main(){
    int n,m;
    while(true){
        cin >> n;
        if(n==0) return 0;
        cin >> m;
        for (int i=1;i<=n;i++){
            pre[i]=i;
        }
        int sum = n-1;
        int a,b;
        for(int i=0;i<m;i++){
            cin >> a >> b;
            if (find(a)==find(b)) continue;
            un(a,b);
            sum--;

        }
        cout << sum << "\n";
    }
    return 0;
}

DZY Loves Chemistry

DZY热爱化学，他喜欢混合化学物质。

DZY有n种化学物质，其中m对会发生反应。他想把这些化学物质倒入试管中，需要一个接一个地倒入，可以任意顺序。

让我们考虑试管的危险性。空试管的危险性为1。每次DZY倒入一种化学物质时，如果试管中已经有一种或多种可以与其发生反应的化学物质，试管的危险性将乘以2。否则，危险性保持不变。

找出在以最佳顺序一个接一个地倒入所有化学物质后的最大可能危险性。

输入
第一行包含两个用空格分隔的整数n和m。

接下来的m行中，每行包含两个用空格分隔的整数xi和yi(1 ≤ xi < yi ≤ n)。这些整数表示化学物质xi将与化学物质yi发生反应。每对化学物质最多只会在输入中出现一次。

考虑所有从1到n编号的化学物质，以某种顺序。

输出
输出一个整数 — 最大可能危险性。

思路

求最终的集合数量

AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int pre[55];

int find(int x){
    if (pre[x]==x) return x;
    else return find(pre[x]);
}

void merge(int a,int b){
    pre[find(a)] = pre[find(b)];
}

int main(){
    int n,m;
    cin >> n >> m;
    //init;
    for (int i=1;i<=n;i++){
        pre[i]=i;
    }
    int a,b;
    for (int i=0;i<m;i++){
        cin >> a >> b;
        merge(a,b);
    }
    int cnt =0 ;
    for (int i=1;i<=n;i++){
        cnt +=(pre[i]==i);
    }
    ll ans;
    ans = pow(2,n-cnt);
    cout << ans << "\n";
    return 0;
}