第一题： 银河英雄传说

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<string,int> PSI;
const int inf = 0x3f3f3f3f;
const int N = 30010;  // 最大战舰数量

int m;  // 指令总数
int p[N], si[N], d[N];  
// p数组：并查集的父节点数组
// si数组：记录每个集合的大小（战舰数量）
// d数组：记录每个战舰到其所在集合根节点的距离

// 并查集的查找函数，带路径压缩和距离维护
int find(int x)
{
    if (p[x] != x)  // 如果x不是根节点
    {
        int root = find(p[x]);  // 递归找到根节点
        d[x] += d[p[x]];  // 维护x到根节点的距离（累加父节点的距离）
        p[x] = root;  // 路径压缩，直接指向根节点
    }
    return p[x];
}
int main()
{
    scanf("%d", &m);  // 读取指令总数
    // 初始化并查集
    for (int i = 1; i < N; i ++ )
    {
        p[i] = i;  // 每个节点的父节点初始化为自己
        si[i] = 1;  // 每个集合的大小初始化为1
    }
    while (m -- )  // 处理每条指令
    {
        char op[2];  // 操作类型
        int a, b;    // 操作涉及的两个战舰编号
        scanf("%s%d%d", op, &a, &b);

        if (op[0] == 'M')  // 如果是合并指令
        {
            int pa = find(a), pb = find(b);  // 找到两个战舰的根节点
            if (pa != pb)  // 如果不在同一集合才需要合并
            {
                d[pa] = si[pb];  // 将pa集合的根节点到pb集合根节点的距离设为pb集合的大小
                si[pb] += si[pa];  // 更新pb集合的大小
                p[pa] = pb;  // 将pa集合合并到pb集合
            }
        }
        else  // 如果是查询指令
        {
            int pa = find(a), pb = find(b);  // 找到两个战舰的根节点
            if (pa != pb) puts("-1");  // 不在同一集合输出-1
            else 
                // 输出两个战舰之间的距离差减1（即中间的战舰数量）
                printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
        }
    }
    return 0;
}

第二题： 围棋4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e5+10;

// 定义四个方向的偏移量：上、下、左、右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

// 定义每个棋块的数据结构
struct node {
    int p;       // 父节点（用于并查集）
    int maxx;    // 棋块中棋子的最大x坐标
    int minx;    // 棋块中棋子的最小x坐标
    int maxy;    // 棋块中棋子的最大y坐标
    int miny;    // 棋块中棋子的最小y坐标
    int s;       // 棋块的覆盖值（矩形面积）
};

node a[22*22];  // 棋盘上每个位置对应的棋块数据（19x19的棋盘，用20x20的数组）
int n;          // 棋子数量
int b[22][22];  // 棋盘，记录每个位置的颜色（1黑/2白）
int ans;        // 当前所有棋块的覆盖值总和

// 合并两个棋块的函数
void solve(int id1, int id2) {
    // 更新棋块2的边界信息，取两个棋块的极值
    a[id2].maxx = max(a[id2].maxx, a[id1].maxx);
    a[id2].minx = min(a[id2].minx, a[id1].minx);
    a[id2].maxy = max(a[id2].maxy, a[id1].maxy);
    a[id2].miny = min(a[id2].miny, a[id1].miny);
    // 重新计算合并后的矩形面积
    a[id2].s = (a[id2].maxx - a[id2].minx + 1) * (a[id2].maxy - a[id2].miny + 1);
    // 将棋块1的父节点指向棋块2（合并）
    a[id1].p = id2;
}

// 并查集的查找函数（带路径压缩）
int find(int x) {
    if (a[x].p != x) {
        int root = find(a[x].p);  // 递归查找根节点
        solve(x, root);           // 路径压缩时合并信息
        a[x].p = root;           // 路径压缩
    }
    return a[x].p;
}

int main() {
    cin >> n;  // 读取棋子数量

    for (int i = 1; i <= n; i++) {
        int c, x, y;
        scanf("%d %d %d", &c, &x, &y);  // 读取棋子颜色和坐标

        // 在棋盘上放置当前棋子
        b[x][y] = c;

        // 计算当前棋子的唯一标识（将二维坐标转换为一维）
        int id = x * 20 + y;

        // 初始化当前棋子的棋块信息
        a[id].p = id;     // 父节点指向自己
        a[id].maxx = x;   // 初始化最大x坐标
        a[id].minx = x;    // 初始化最小x坐标
        a[id].maxy = y;   // 初始化最大y坐标
        a[id].miny = y;    // 初始化最小y坐标
        a[id].s = (a[id].maxx - a[id].minx + 1) * (a[id].maxy - a[id].miny + 1);  // 计算初始面积

        // 将当前棋块的面积加入总和
        ans += a[id].s;

        // 检查四个方向的相邻位置
        for (int j = 0; j < 4; j++) {
            int nx = x + dx[j];
            int ny = y + dy[j];

            // 如果相邻位置在棋盘内且颜色相同
            if (b[x][y] == b[nx][ny] && nx >= 1 && ny >= 1 && nx <= 19 && ny <= 19) {
                int idd = nx * 20 + ny;  // 相邻位置的唯一标识

                // 查找当前棋子和相邻棋子的根节点
                int pa = find(id), pb = find(idd);

                // 如果两个棋子不属于同一个棋块
                if (pa != pb) {
                    // 从总和中减去两个棋块的面积
                    ans -= a[pa].s;
                    ans -= a[pb].s;

                    // 合并两个棋块（将pa合并到pb中）
                    solve(pa, pb);
                    a[pa].p = pb;

                    // 将合并后的新面积加入总和
                    ans += a[pb].s;
                }
            }
        }

        // 输出当前所有棋块的覆盖值总和
        printf("%d ", ans);
    }

    return 0;
}

第三题： 森林1
d[x]:以x为根节点的数的最大高度 ，维护d[x]。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e5+10;
int p[1000010];
int d[1000010];
int n,m;
int ans=-1;
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        d[i]=1;
    }
    while(m--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        int pa=find(a);
        int pb=find(b);
        if(pa!=pb)
        {
            d[pb]=max(d[pb],d[pa]+1);
            p[pa]=pb;
            cout<<d[pb]<<" ";
        }
        else printf("0 ");
    }
    return 0;
}

第四题： 铁索连环(boat)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<int,int>
const int N=1e5+10;
int n,m;
int p[1010];
int d[1010];
vector<int> q;
bool st[1010];
int find(int x)
{
    if(x!=p[x])
    {
        st[x]=true;
        int t=find(p[x]);
        p[x]=t;
    }
    return p[x];
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        p[i]=i;
        scanf("%d",&d[i]);
    }
    while(m--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        int pa=find(a);
        int pb=find(b);
        if(pa!=pb)
        {
            d[pb]+=d[pa];
            p[pa]=pb;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(!st[i]&&p[i]==i)
        {
            q.push_back(d[i]);
        }
    }
    cout<<q.size()<<endl;
    sort(q.begin(),q.end());
    for(int i=0;i<q.size();i++) cout<<q[i]<<" ";

    return 0;
}