题解

我写的应该有bug但是我懒得改了

就是最后一次合并的n要么是0点边集的最后一条边，要么是0点边集最后两条边的差，我们分别拎出来判断一下哪个可行（也许两个都可行，但是我不想多做修改了……）

然后递归处理两边……

代码

#include <bits/stdc++.h>

#define enter putchar('\n')

#define space putchar(' ')

#define pii pair<int,int>

#define fi first

#define se second

#define MAXN 100005

#define pb push_back

#define mp make_pair

#define eps 1e-8

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

        if(c == '-') f = -1;

        c = getchar();

    }

    while(c >= '0' && c <= '9') {

        res = res * 10 + c - '0';

        c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) out(x / 10);

    putchar('0' + x % 10);

}

bool dcmp(db a,db b) {

    return fabs(a - b) < eps;

}

int T,N,M;

vector<int> E[MAXN];

map<pii,bool> mmm;

bool F;

void Init() {

    read(N);read(M);

    F = 1;

    int u,v;

    for(int i = 0 ; i < N ; ++i) E[i].clear();

    mmm.clear();

    for(int i = 1 ; i <= M ; ++i) {

        read(u);read(v);

        if(u > v) swap(u,v);

        if(u == v) F = 0;

        else if(mmm[mp(u,v)]) F = 0;

        mmm[mp(u,v)] = 1;

        E[u].pb(v);

    }

    for(int i = 0 ; i < N ; ++i) sort(E[i].begin(),E[i].end());

}

bool Exist(int l,int r) {

    if(l == r) {

        if(!E[l].size()) return true;

        else return false;

    }

    int s = E[l].size(),n;

    if(!s) return false;

    if(s == 1) n = E[l][s - 1] - l;

    else {

        n = E[l][s - 1] - E[l][s - 2];

        bool flag = 1;

        if(n * 2 > (r - l + 1)) flag = false;

        for(int i = 0 ; i < n ; ++i) {

            int p = (r - l - i) / n;

            if(E[l + i].size() < p) {flag = false;break;}

            s = E[l + i].size() - 1;

            for(int j = p ; j >= 1 ; --j) {

                if(E[l + i][s] != l + j * n + i) {flag = false;break;}

                --s;

            }

        }

        s = E[l].size();

        if(!flag) n = E[l][s - 1] - l;

    }

    if(n * 2 > (r - l + 1)) return false;

    for(int i = 0 ; i < n ; ++i) {

        int p = (r - l - i) / n;

        if(E[l + i].size() < p) return false;

        s = E[l + i].size() - 1;

        for(int j = p ; j >= 1 ; --j) {

            if(E[l + i][s] != l + j * n + i) return false;

            --s;

        }

    }

    for(int i = l ; i <= l + n - 1 ; ++i) {

        int s = E[i].size() - 1;

        while(s >= 0) {

            if(E[i][s] >= l + n) E[i].pop_back();

            else break;

            s--;

        }

    }

    return Exist(l,l + n - 1) && Exist(l + n,r);

}

void Solve() {

    if(F && Exist(0,N - 1)) puts("YES");

    else puts("NO");

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    int T;

    read(T);

    while(T--) {

        Init();

        Solve();

    }

    return 0;

}