B. Seating in a Bus

Link

Solution

裸的并查集，注意边缘情况即可。

Code

const int maxn = 200010;

int a[maxn];

class DS {
private:
    int rt[maxn];

public:
    int count;  // 连通分量的个数
    DS(int n)
    {
        count = n;
        for (size_t i = 1; i <= n; i++) rt[i] = i;
    }

    int find_rt(int x)
    {
        if (rt[x] == x) return x;
        else
            return rt[x] = find_rt(rt[x]);
    }

    void merge(int x, int y)
    {
        int xrt = find_rt(x);
        int yrt = find_rt(y);
        if (xrt != yrt) {
            rt[xrt] = yrt;
            count--;
        }
    }

    bool is_connected(int x, int y) { return find_rt(x) == find_rt(y); }
};

int main() {
    int n, t;
    std::cin >> t;
    while (t--) {
        memset(a, 0, maxn);
        std::cin >> n;
        DS ds = DS(n);
        for (size_t i = 0; i < n; i++) std::cin >> a[i];
        if (a[0] == n) ds.merge(a[0], a[0] - 1);
        else if (a[0] == 1) ds.merge(a[0], a[0] + 1);
        else {
            ds.merge(a[0], a[0] + 1);
            ds.merge(a[0], a[0] - 1);
        }
        int flag = 1;
        for (size_t i = 1; i < n; i++) {
            if (ds.is_connected(a[i - 1], a[i])) {
                if (a[i] == n) ds.merge(a[i], a[i] - 1);
                else if (a[i] == 1)
                    ds.merge(a[i], a[i] + 1);
                else {
                    ds.merge(a[i], a[i] + 1);
                    ds.merge(a[i], a[i] - 1);
                }
            }
            else {
                flag = 0;
                break;
            }
        }
        if (flag) std::cout << "YES" << std::endl;
        else
            std::cout << "NO" << std::endl;
    }
    return 0;
}