跳至主要內容
ACM常用代码模版

ACM常用代码模版

数据结构

并查集

struct DSU {
    std::vector<int> f, siz;

    DSU(int n) {
        f.resize(n + 1);
        siz.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            f[i] = i;
            siz[i] = 1;
        }
    }

    int find(int x) {
        if (x != f[x]) f[x] = find(f[x]);
        return f[x];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};
全民制作人ikun小于 1 分钟AlgorithmACMAlgorithmACM
C++的STL在ACM算法竞赛中的应用

C++的STL容器在ACM算法竞赛中的应用

一些有用的函数

is_sorted(a.begin(),a.end(),cmp);

判断是否按照cmp中的规则排序，默认升序

用法：

vector<int> a(10);
bool ok = is_sorted(a.begin() + 1, a.end());
cout << ok << endl;
全民制作人ikun大约 3 分钟C++ACMC++ACM