【算法笔记自学】第 9 章提高篇（3）—

9.1树与二叉树

#include <cstdio>

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    printf(n == m + 1 ? "Yes" : "No");
    return 0;
}

9.2二叉树的遍历

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 50;

struct Node {
    int l, r;
} nodes[MAXN];

vector<int> pre;

void preOrder(int root) {
    if (root == -1) {
        return;
    }
    pre.push_back(root);
    preOrder(nodes[root].l);
    preOrder(nodes[root].r);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &nodes[i].l, &nodes[i].r);
    }
    preOrder(0);
    for (int i = 0; i < (int)pre.size(); i++) {
        printf("%d", pre[i]);
        if (i < (int)pre.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 50;

struct Node {
    int l, r;
} nodes[MAXN];

vector<int> pre;

void preOrder(int root) {
    if (root == -1) {
        return;
    }
    preOrder(nodes[root].l);
    pre.push_back(root);
    preOrder(nodes[root].r);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &nodes[i].l, &nodes[i].r);
    }
    preOrder(0);
    for (int i = 0; i < (int)pre.size(); i++) {
        printf("%d", pre[i]);
        if (i < (int)pre.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 50;

struct Node {
    int l, r;
} nodes[MAXN];

vector<int> pre;

void preOrder(int root) {
    if (root == -1) {
        return;
    }
    preOrder(nodes[root].l);
    preOrder(nodes[root].r);
    pre.push_back(root);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &nodes[i].l, &nodes[i].r);
    }
    preOrder(0);
    for (int i = 0; i < (int)pre.size(); i++) {
        printf("%d", pre[i]);
        if (i < (int)pre.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 50;

struct Node {
    int l, r;
} nodes[MAXN];

vector<int> layer;

void layerOrder(int root) {
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int front = q.front();
        q.pop();
        layer.push_back(front);
        if (nodes[front].l != -1) {
            q.push(nodes[front].l);
        }
        if (nodes[front].r != -1) {
            q.push(nodes[front].r);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &nodes[i].l, &nodes[i].r);
    }
    layerOrder(0);
    for (int i = 0; i < (int)layer.size(); i++) {
        printf("%d", layer[i]);
        if (i < (int)layer.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 50;

struct Node {
    int l, r;
} nodes[MAXN];

int getHeight(int root) {
    if (root == -1) {
        return 0;
    }
    int leftHeight = getHeight(nodes[root].l);
    int rightHeight = getHeight(nodes[root].r);
    return max(leftHeight, rightHeight) + 1;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &nodes[i].l, &nodes[i].r);
    }
    printf("%d", getHeight(0));
    return 0;
}

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 50;

struct Node {
    int l, r;
} nodes[MAXN];

int layers[MAXN];

void layerOrder(int root) {
    queue<int> q;
    q.push(root);
    int layer = 1;
    while (!q.empty()) {
        int cnt = q.size();
        for (int i = 0; i < cnt; i++) {
            int front = q.front();
            q.pop();
            layers[front] = layer;
            if (nodes[front].l != -1) {
                q.push(nodes[front].l);
            }
            if (nodes[front].r != -1) {
                q.push(nodes[front].r);
            }
        }
        layer++;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &nodes[i].l, &nodes[i].r);
    }
    layerOrder(0);
    for (int i = 0; i < n; i++) {
        printf("%d", layers[i]);
        if (i < n - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 50;

struct Node {
    int l, r;
} nodes[MAXN];

vector<int> pre, in, post;

int buildTree(int preL, int preR, int inL, int inR) {
    if (preL > preR) {
        return -1;
    }
    int root = pre[preL];
    int inIndexOfRoot;
    for (int i = inL; i <= inR; i++) {
        if (in[i] == root) {
            inIndexOfRoot = i;
            break;
        }
    }
    int leftCount = inIndexOfRoot - inL;
    nodes[root].l = buildTree(preL + 1, preL + leftCount, inL, inIndexOfRoot - 1);
    nodes[root].r = buildTree(preL + leftCount + 1, preR, inIndexOfRoot + 1, inR);
    return root;
}

void postOrder(int root) {
    if (root == -1) {
        return;
    }
    postOrder(nodes[root].l);
    postOrder(nodes[root].r);
    post.push_back(root);
}

int main() {
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        pre.push_back(x);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        in.push_back(x);
    }
    int root = buildTree(0, n - 1, 0, n - 1);
    postOrder(root);
    for (int i = 0; i < (int)post.size(); i++) {
        printf("%d", post[i]);
        if (i < (int)post.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 50;

struct Node {
    int l, r;
} nodes[MAXN];

vector<int> pre, in, post;

int buildTree(int postL, int postR, int inL, int inR) {
    if (postL > postR) {
        return -1;
    }
    int root = post[postR];
    int inIndexOfRoot;
    for (int i = inL; i <= inR; i++) {
        if (in[i] == root) {
            inIndexOfRoot = i;
            break;
        }
    }
    int leftCount = inIndexOfRoot - inL;
    nodes[root].l = buildTree(postL, postL + leftCount - 1, inL, inIndexOfRoot - 1);
    nodes[root].r = buildTree(postL + leftCount, postR - 1, inIndexOfRoot + 1, inR);
    return root;
}

void preOrder(int root) {
    if (root == -1) {
        return;
    }
    pre.push_back(root);
    preOrder(nodes[root].l);
    preOrder(nodes[root].r);
}

int main() {
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        post.push_back(x);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        in.push_back(x);
    }
    int root = buildTree(0, n - 1, 0, n - 1);
    preOrder(root);
    for (int i = 0; i < (int)pre.size(); i++) {
        printf("%d", pre[i]);
        if (i < (int)pre.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <map>
#include <vector>
using namespace std;

const int MAXN = 50;

struct Node {
    int l, r;
} nodes[MAXN];

vector<int> pre, in, layer;

int buildTree(vector<int> layer, int inL, int inR) {
    if (layer.empty()) {
        return -1;
    }
    int root = layer[0];
    map<int, bool> isLeft;
    int inIndexOfRoot;
    for (int i = inL; i <= inR; i++) {
        if (in[i] == root) {
            inIndexOfRoot = i;
            break;
        } else {
            isLeft[in[i]] = true;
        }
    }
    vector<int> leftLayer, rightLayer;
    for (int i = 1; i < layer.size(); i++) {
        if (isLeft[layer[i]]) {
            leftLayer.push_back(layer[i]);
        } else {
            rightLayer.push_back(layer[i]);
        }
    }
    nodes[root].l = buildTree(leftLayer, inL, inIndexOfRoot - 1);
    nodes[root].r = buildTree(rightLayer, inIndexOfRoot + 1, inR);
    return root;
}

void preOrder(int root) {
    if (root == -1) {
        return;
    }
    pre.push_back(root);
    preOrder(nodes[root].l);
    preOrder(nodes[root].r);
}

int main() {
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        layer.push_back(x);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        in.push_back(x);
    }
    int root = buildTree(layer, 0, n - 1);
    preOrder(root);
    for (int i = 0; i < (int)pre.size(); i++) {
        printf("%d", pre[i]);
        if (i < (int)pre.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 50;

struct Node {
    int data;
    int l, r;
} nodes[MAXN];

int treePathSum = 0;

void getTreePathSum(int root, int nodePathSum) {
    if (root == -1) {
        return;
    }
    nodePathSum += nodes[root].data;
    if (nodes[root].l == -1 && nodes[root].r == -1) {
        treePathSum += nodePathSum;
    } else {
        getTreePathSum(nodes[root].l, nodePathSum);
        getTreePathSum(nodes[root].r, nodePathSum);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nodes[i].data);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &nodes[i].l, &nodes[i].r);
    }
    getTreePathSum(0, 0);
    printf("%d", treePathSum);
    return 0;
}

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 50;

struct Node {
    int data;
    int l, r;
} nodes[MAXN];

int treeWeightedPathLength = 0;

void getTreeWeightedPathLength(int root, int nodePathLength) {
    if (root == -1) {
        return;
    }
    if (nodes[root].l == -1 && nodes[root].r == -1) {
        treeWeightedPathLength += nodes[root].data * nodePathLength;
    } else {
        nodePathLength++;
        getTreeWeightedPathLength(nodes[root].l, nodePathLength);
        getTreeWeightedPathLength(nodes[root].r, nodePathLength);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nodes[i].data);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &nodes[i].l, &nodes[i].r);
    }
    getTreeWeightedPathLength(0, 0);
    printf("%d", treeWeightedPathLength);
    return 0;
}

9.3树的遍历

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 50;

struct Node {
    vector<int> children;
} nodes[MAXN];

vector<int> pre;

void preOrder(int root) {
    pre.push_back(root);
    for (int i = 0; i < nodes[root].children.size(); i++) {
        preOrder(nodes[root].children[i]);
    }
}

int main() {
    int n, k, child;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &child);
            nodes[i].children.push_back(child);
        }
    }
    preOrder(0);
    for (int i = 0; i < pre.size(); i++) {
        printf("%d", pre[i]);
        if (i < (int)pre.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 50;

struct Node {
    vector<int> children;
} nodes[MAXN];

vector<int> post;

void postOrder(int root) {
    for (int i = 0; i < nodes[root].children.size(); i++) {
        postOrder(nodes[root].children[i]);
    }
    post.push_back(root);
}

int main() {
    int n, k, child;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &child);
            nodes[i].children.push_back(child);
        }
    }
    postOrder(0);
    for (int i = 0; i < post.size(); i++) {
        printf("%d", post[i]);
        if (i < (int)post.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 50;

struct Node {
    vector<int> children;
} nodes[MAXN];

vector<int> layer;

void layerOrder(int root) {
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int front = q.front();
        q.pop();
        layer.push_back(front);
        for (int i = 0; i < nodes[front].children.size(); i++) {
            q.push(nodes[front].children[i]);
        }
    }
}

int main() {
    int n, k, child;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &child);
            nodes[i].children.push_back(child);
        }
    }
    layerOrder(0);
    for (int i = 0; i < layer.size(); i++) {
        printf("%d", layer[i]);
        if (i < (int)layer.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 50;

struct Node {
    int data;
    vector<int> children;
} nodes[MAXN];

int treePathSum = 0;

void getTreePathSum(int root, int nodePathSum) {
    nodePathSum += nodes[root].data;
    if (nodes[root].children.empty()) {
        treePathSum += nodePathSum;
    }
    for (int i = 0; i < nodes[root].children.size(); i++) {
        getTreePathSum(nodes[root].children[i], nodePathSum);
    }
}

int main() {
    int n, k, child;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nodes[i].data);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &child);
            nodes[i].children.push_back(child);
        }
    }
    getTreePathSum(0, 0);
    printf("%d", treePathSum);
    return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 50;

struct Node {
    int data;
    vector<int> children;
} nodes[MAXN];

int treePathLength = 0;

void getTreePathLength(int root, int edgeCount) {
    if (nodes[root].children.empty()) {
        treePathLength += nodes[root].data * edgeCount;
    }
    for (int i = 0; i < nodes[root].children.size(); i++) {
        getTreePathLength(nodes[root].children[i], edgeCount + 1);
    }
}

int main() {
    int n, k, child;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nodes[i].data);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &child);
            nodes[i].children.push_back(child);
        }
    }
    getTreePathLength(0, 0);
    printf("%d", treePathLength);
    return 0;
}

9.4二叉查找树（BST）

#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 50;

struct Node {
    int data;
    int l, r;
} nodes[MAXN];

int nodeCount = 0;

int newNode(int data) {
    nodes[nodeCount].data = data;
    nodes[nodeCount].l = nodes[nodeCount].r = -1;
    return nodeCount++;
}

int insert(int root, int data) {
    if (root == -1) {
        return newNode(data);
    }
    if (data < nodes[root].data) {
        nodes[root].l = insert(nodes[root].l, data);
    } else {
        nodes[root].r = insert(nodes[root].r, data);
    }
    return root;
}

vector<int> pre;

void preOrder(int root) {
    if (root == -1) {
        return;
    }
    pre.push_back(nodes[root].data);
    preOrder(nodes[root].l);
    preOrder(nodes[root].r);
}

int main() {
    int n, data, root = -1;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &data);
        root = insert(root, data);
    }
    preOrder(root);
    for (int i = 0; i < (int)pre.size(); i++) {
        printf("%d", pre[i]);
        if (i < (int)pre.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <vector>
using namespace std;

vector<int> in;

bool isBST() {
    for (int i = 1; i < in.size(); i++) {
        if (in[i] <= in[i - 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        in.push_back(x);
    }
    printf(isBST() ? "Yes" : "No");
    return 0;
}

9.5平衡二叉树（AVL树）

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 50;

struct Node {
    int data;
    int height;
    int l, r;
} nodes[MAXN];

int nodeCount = 0;

int newNode(int data) {
    nodes[nodeCount].data = data;
    nodes[nodeCount].height = 1;
    nodes[nodeCount].l = nodes[nodeCount].r = -1;
    return nodeCount++;
}

int getHeight(int root) {
    if (root == -1) {
        return 0;
    } else {
        return nodes[root].height;
    }
}

void updateHeight(int root) {
    nodes[root].height = max(getHeight(nodes[root].l), getHeight(nodes[root].r)) + 1;
}

int getBalanceFactor(int root) {
    return getHeight(nodes[root].l) - getHeight(nodes[root].r);
}

int insert(int root, int data) {
    if (root == -1) {
        return newNode(data);
    }
    if (data < nodes[root].data) {
        nodes[root].l = insert(nodes[root].l, data);
    } else {
        nodes[root].r = insert(nodes[root].r, data);
    }
    updateHeight(root);
    return root;
}

vector<int> balanceFactor;

void inOrder(int root) {
    if (root == -1) {
        return;
    }
    inOrder(nodes[root].l);
    balanceFactor.push_back(getBalanceFactor(root));
    inOrder(nodes[root].r);
}

int main() {
    int n, data, root = -1;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &data);
        root = insert(root, data);
    }
    inOrder(root);
    for (int i = 0; i < (int)balanceFactor.size(); i++) {
        printf("%d", balanceFactor[i]);
        if (i < (int)balanceFactor.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 50;

struct Node {
    int data;
    int height;
    int l, r;
} nodes[MAXN];

int nodeCount = 0;

int newNode(int data) {
    nodes[nodeCount].data = data;
    nodes[nodeCount].height = 1;
    nodes[nodeCount].l = nodes[nodeCount].r = -1;
    return nodeCount++;
}

int getHeight(int root) {
    if (root == -1) {
        return 0;
    } else {
        return nodes[root].height;
    }
}

void updateHeight(int root) {
    nodes[root].height = max(getHeight(nodes[root].l), getHeight(nodes[root].r)) + 1;
}

int getBalanceFactor(int root) {
    return getHeight(nodes[root].l) - getHeight(nodes[root].r);
}

int insert(int root, int data) {
    if (root == -1) {
        return newNode(data);
    }
    if (data < nodes[root].data) {
        nodes[root].l = insert(nodes[root].l, data);
    } else {
        nodes[root].r = insert(nodes[root].r, data);
    }
    updateHeight(root);
    return root;
}

bool isAVL(int root) {
    if (root == -1) {
        return true;
    }
    return isAVL(nodes[root].l) && isAVL(nodes[root].r) && abs(getBalanceFactor(root)) <= 1;
}

int main() {
    int n, data, root = -1;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &data);
        root = insert(root, data);
    }
    printf(isAVL(root) ? "Yes" : "No");
    return 0;
}

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 50;

struct Node {
    int data;
    int height;
    int l, r;
} nodes[MAXN];

int nodeCount = 0;

int newNode(int data) {
    nodes[nodeCount].data = data;
    nodes[nodeCount].height = 1;
    nodes[nodeCount].l = nodes[nodeCount].r = -1;
    return nodeCount++;
}

int getHeight(int root) {
    if (root == -1) {
        return 0;
    } else {
        return nodes[root].height;
    }
}

void updateHeight(int root) {
    nodes[root].height = max(getHeight(nodes[root].l), getHeight(nodes[root].r)) + 1;
}

int getBalanceFactor(int root) {
    return getHeight(nodes[root].l) - getHeight(nodes[root].r);
}

int L(int root) {
    int temp = nodes[root].r;
    nodes[root].r = nodes[temp].l;
    nodes[temp].l = root;
    updateHeight(root);
    updateHeight(temp);
    return temp;
}

int R(int root) {
    int temp = nodes[root].l;
    nodes[root].l = nodes[temp].r;
    nodes[temp].r = root;
    updateHeight(root);
    updateHeight(temp);
    return temp;
}

int insert(int root, int data) {
    if (root == -1) {
        return newNode(data);
    }
    if (data < nodes[root].data) {
        nodes[root].l = insert(nodes[root].l, data);
        updateHeight(root);
        if (getBalanceFactor(root) == 2) {
            if (getBalanceFactor(nodes[root].l) == 1) {
                root = R(root);
            } else if (getBalanceFactor(nodes[root].l) == -1) {
                nodes[root].l = L(nodes[root].l);
                root = R(root);
            }
        }
    } else {
        nodes[root].r = insert(nodes[root].r, data);
        updateHeight(root);
        if (getBalanceFactor(root) == -2) {
            if (getBalanceFactor(nodes[root].r) == -1) {
                root = L(root);
            } else if (getBalanceFactor(nodes[root].r) == 1) {
                nodes[root].r = R(nodes[root].r);
                root = L(root);
            }
        }
    }
    return root;
}

vector<int> pre;

void preOrder(int root) {
    if (root == -1) {
        return;
    }
    pre.push_back(nodes[root].data);
    preOrder(nodes[root].l);
    preOrder(nodes[root].r);
}

int main() {
    int n, data, root = -1;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &data);
        root = insert(root, data);
    }
    preOrder(root);
    for (int i = 0; i < (int)pre.size(); i++) {
        printf("%d", pre[i]);
        if (i < (int)pre.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

9.6并查集

#include <cstdio>
#include <cstring>

const int MAXN = 100;
int father[MAXN];

int findFather(int x) {
    int xCopy = x;
    while (father[x] != x) {
        x = father[x];
    }
    int root = x;
    x = xCopy;
    while (father[x] != x) {
        int fatherX = father[x];
        father[x] = root;
        x = fatherX;
    }
    return root;
}

void unionSet(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB) {
        father[faA] = faB;
    }
}

void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}

int main() {
    int n, m, a, b;
    scanf("%d%d", &n, &m);
    init(n);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        unionSet(a - 1, b - 1);
    }
    int classCount = 0;
    for (int i = 0; i < n; i++) {
        if (father[i] == i) {
            classCount++;
        }
    }
    printf("%d", classCount);
    return 0;
}

#include <cstdio>
#include <cstring>

const int MAXN = 100;
int father[MAXN];

int findFather(int x) {
    int xCopy = x;
    while (father[x] != x) {
        x = father[x];
    }
    int root = x;
    x = xCopy;
    while (father[x] != x) {
        int fatherX = father[x];
        father[x] = root;
        x = fatherX;
    }
    return root;
}

void unionSet(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB) {
        father[faA] = faB;
    }
}

void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}

int main() {
    int n, m, a, b;
    scanf("%d%d", &n, &m);
    init(n);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        unionSet(a - 1, b - 1);
    }
    bool linked = true;
    for (int i = 1; i < n; i++) {
        if (findFather(i) != findFather(0)) {
            linked = false;
        }
    }
    printf(linked ? "Yes" : "No");
    return 0;
}

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100;
int father[MAXN];
int score[MAXN];

vector<int> classes;

int findFather(int x) {
    int xCopy = x;
    while (father[x] != x) {
        x = father[x];
    }
    int root = x;
    x = xCopy;
    while (father[x] != x) {
        int fatherX = father[x];
        father[x] = root;
        x = fatherX;
    }
    return root;
}

void unionSet(int a, int b) {
    int faA = findFather(a);
    int faB = findFather(b);
    if (faA != faB) {
        if (score[faA] < score[faB]) {
            father[faA] = faB;
        } else {
            father[faB] = faA;
        }
    }
}

void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}

int main() {
    int n, m, a, b;
    scanf("%d%d", &n, &m);
    init(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &score[i]);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        unionSet(a - 1, b - 1);
    }
    for (int i = 0; i < n; i++) {
        if (findFather(i) == i) {
            classes.push_back(score[i]);
        }
    }
    sort(classes.rbegin(), classes.rend());
    printf("%d\n", (int)classes.size());
    for (int i = 0; i < classes.size(); i++) {
        printf("%d", classes[i]);
        if (i < (int)classes.size() - 1) {
            printf(" ");
        }
    }
    return 0;
}

9.7堆

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1000 + 1;
int heap[MAXN];

void downAdjust(int low, int high) {
    int i = low, j = i * 2;
    while (j <= high) {
        if (j + 1 <= high && heap[j + 1] > heap[j]) {
            j = j + 1;
        }
        if (heap[j] > heap[i]) {
            swap(heap[j], heap[i]);
            i = j;
            j = i * 2;
        } else {
            break;
        }
    }
}

void createHeap(int n) {
    for (int i = n / 2; i >= 1; i--) {
        downAdjust(i, n);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &heap[i]);
    }
    createHeap(n);
    for (int i = 1; i <= n; i++) {
        printf("%d", heap[i]);
        if (i < n) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1000 + 1;
int heap[MAXN];

void downAdjust(int low, int high) {
    int i = low, j = i * 2;
    while (j <= high) {
        if (j + 1 <= high && heap[j + 1] > heap[j]) {
            j = j + 1;
        }
        if (heap[j] > heap[i]) {
            swap(heap[j], heap[i]);
            i = j;
            j = i * 2;
        } else {
            break;
        }
    }
}

void createHeap(int n) {
    for (int i = n / 2; i >= 1; i--) {
        downAdjust(i, n);
    }
}

int deleteTop(int n) {
    if (n > 0) {
        heap[1] = heap[n--];
        downAdjust(1, n);
    }
    return n;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &heap[i]);
    }
    createHeap(n);
    n = deleteTop(n);
    for (int i = 1; i <= n; i++) {
        printf("%d", heap[i]);
        if (i < n) {
            printf(" ");
        }
    }
    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 50 + 1;
int heap[MAXN];

void downAdjust(int low, int high) {
    int i = low, j = i * 2;
    while (j <= high) {
        if (j + 1 <= high && heap[j + 1] > heap[j]) {
            j = j + 1;
        }
        if (heap[j] > heap[i]) {
            swap(heap[j], heap[i]);
            i = j;
            j = i * 2;
        } else {
            break;
        }
    }
}

void createHeap(int n) {
    for (int i = n / 2; i >= 1; i--) {
        downAdjust(i, n);
    }
}

void heapSort(int n) {
    createHeap(n);
    for (int i = n; i > 1; i--) {
        swap(heap[i], heap[1]);
        downAdjust(1, i - 1);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &heap[i]);
    }
    heapSort(n);
    for (int i = 1; i <= n; i++) {
        printf("%d", heap[i]);
        if (i < n) {
            printf(" ");
        }
    }
    return 0;
}

9.8哈夫曼树

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int minCostToMergeFruits(vector<int>& fruits) {
    // 使用优先队列（最小堆）来处理
    priority_queue<int, vector<int>, greater<int>> minHeap(fruits.begin(), fruits.end());
    
    int totalCost = 0;
    
    // 当堆中还有超过一个元素时，进行合并操作
    while (minHeap.size() > 1) {
        // 取出最小的两个果堆
        int first = minHeap.top();
        minHeap.pop();
        int second = minHeap.top();
        minHeap.pop();
        
        // 合并这两个果堆
        int mergedCost = first + second;
        totalCost += mergedCost;
        
        // 将新的合并后的果堆放回堆中
        minHeap.push(mergedCost);
    }
    
    return totalCost;
}

int main() {
    int n;
    cin >> n;
    vector<int> fruits(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> fruits[i];
    }
    
    int result = minCostToMergeFruits(fruits);
    cout << result << endl;
    
    return 0;
}

#include <cstdio>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, greater<int> > pq;

int main() {
    int n, weight;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &weight);
        pq.push(weight);
    }
    int ans = 0;
    while (pq.size() > 1) {
        int top1 = pq.top();
        pq.pop();
        int top2 = pq.top();
        pq.pop();
        pq.push(top1 + top2);
        ans += top1 + top2;
    }
    printf("%d", ans);
    return 0;
}

#include <iostream>
#include <string>
#include <queue>
using namespace std;

const int MAXC = 26;
int charCnt[MAXC] = {0};

priority_queue<int, vector<int>, greater<int> > pq;

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        charCnt[s[i] - 'A']++;
    }
    for (int i = 0; i < MAXC; i++) {
        if (charCnt[i] > 0) {
            pq.push(charCnt[i]);
        }
    }
    int ans = 0;
    while (pq.size() > 1) {
        int top1 = pq.top();
        pq.pop();
        int top2 = pq.top();
        pq.pop();
        pq.push(top1 + top2);
        ans += top1 + top2;
    }
    printf("%d", ans);
    return 0;
}