并查集模板

这套模板适合所有使用并查集的题目，无论是检测是否连通，还是构造最小生成树。

节点怎么定义

1、利用节点ID定义；
2、若节点输入为char，转换为1-n的整数；
3、若没有给出明确的节点定义特征，可以使用输入顺序order表示两点，请看例题：Freckles

是否调用queue

1、若需要求最小生成树，例如最小消耗，最短距离等，可以使用priority_queue，其具体用法可自行搜索；
2、若仅判断图是否连通，还有多少顶点未连通，可以不调用queue库

#include <iostream>
#include <queue> // 一会调用优先队列
using namespace std;
#define MAX 100 // 最大尺寸，在题目给出数据过多时，可自行调整

int root[MAX];  // 每棵树的根节点
int high[MAX];  // 每棵树的高度

void Initial(int n) // 初始化
{
    for(int i = 0;i<=n;i++) // 一般从1开始到n，也有从0到n-1的，全部包括进去，检查时去除边界点
    {
        root[i] = i;
        high[i] = 0;
    }
}

int find(int x) // 找到自己的根节点
{
    if( x != root[x])
        root[x] = find(root[x]); // 递归调用寻找根节点
    return root[x];
}

bool Union(int x,int y) // 在一些简单情况下可以使用不包括返回值的联通函数
{
    x = find(x); // x的跟
    y = find(y); // y的跟
    if(x == y) return false; // 二者是同一棵树，无需连通
    else
    {
        if(high[x] < high[y]) // 把树x作为y的子树
        // 注意：x树仅根节点变化，其他分支及叶节点跟还是指向x，但是在find调用时会修改掉
        {
            root[x] = y;
        }
        else if(high[x] > high[y])
        {
            root[y] = x;
        }
        else // 二者等高
        {
            root[x] = y; // x作为y的子树
            high[y]++;  // y最大高度加一
        }
        return true; // 传进来的x，y需要联通
    }
}

struct edge // 边界点
{
    int start,end,cost; // 起点，终点，花费
    edge(int x,int y,int z)
    {
        start = x;
        end = y;
        cost = z;
    }
    edge(){}
    bool operator<(const edge& e) const // 为了调用优先队列重定义<
    {
        return cost > e.cost;
    }
};

int main()
{
    int n,m,min_cost,len;
    edge e;
    while(cin >> n >> m)
    {
        priority_queue<edge> q; // 根据重定义后的结果，此时cost小的路径在顶部
        Initial(m); // 初始化
        for(int i = 0;i<n;i++)
        {
            cin >> e.start >> e.end >> e.cost;
            q.push(e);
        }
        if(n < m-1) // 无向图连通最小边数为顶点数-1
        {
            cout << "?" << endl;
            continue;
        }
        len = m-1; // 最小边数，当len为0时，代表图中已经有顶点-1条边，连通
        min_cost = 0; // 最小花费
        while(len && !q.empty())
        {
            e = q.top(); // 克鲁斯卡尔算法，每次取最小路径
            q.pop();
            if(Union(e.start, e.end)) // 路径两端是否连通
            {
                len--; // 边加一
                min_cost += e.cost; // 修路
            }
        }
        if(len) cout << "?" << endl; // len == 0表示图连通，否则不连通
        else cout << min_cost << endl; 
    }
}