乱搞构造
想到判断是否可行，可以找一个分割点，判断能否在此分割，递归左右两边
但是！！只有一个分割点可行（抽象理解一下，后面的向前面的点循环连边，若移动分割点会打坏循环）
如何找到这个点呢？
方法很多，仔细想想都可以想到，这里提供一种思路
遍历第一个点（即0号点）的连边情况，找到一个分割点使得其余边与此点形成倍数关系，剩下的点刚好形成剩下的边数个循环，当然还有前半部分要小于后半部分（具体看代码理解一下就好）
时间复杂度(O(nlog_n))
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int N=1e5+4;
vector<int>e[N];
set<int>st[N];
int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
bool solve(int l,int r){
if(l==r)return 1;
if(l>r||e[l].empty())return 0;
int d=e[l][e[l].size()-1]-l,id=-1,cnt=0;
for(int i=e[l].size()-1,u;i>=0;i--){
u=e[l][i];cnt++;
if(gcd(u-l,d)==u-l&&(r-l)/(u-l)==cnt&&r-u+1>=u-l){id=u;break;}
}
if(id==-1)return 0;
for(int i=l,u;i<id;i++){
u=(r-i)/(id-l);
while(u){
if(e[i][e[i].size()-1]!=i+(id-l)*u)return 0;
u--;
e[i].pop_back();
}
}
return solve(l,id-1)&&solve(id,r);
}
int main(){
int T=read(),n,m,fl;
while(T--){
n=read();m=read();
fl=0;
for(int i=0;i<n;i++){e[i].clear();st[i].clear();}
for(int i=1,u,v;i<=m;i++){
u=read();v=read();
if(u==v)fl=1;
if(u>v)u^=v^=u^=v;
if(!st[u].count(v)){st[u].insert(v);e[u].push_back(v);}
else fl=1;
}
if(fl){puts("NO");continue;}
for(int i=0;i<n;i++)sort(e[i].begin(),e[i].end());
if(solve(0,n-1))puts("YES");
else puts("NO");
}
return (0-0);
}
mine:
从后面开始，找到一个循环即可得知断开的长度，不符合的情况根据不同的样例判一下就好
注意判重边自环
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int N=1e5+4;
int n,m,vis[N];
vector<int>e[N];
bool solve(int l,int r){
if(l>=r)return 1;
int duan=-1;
for(int i=r,pre,u,mx;i>=l;i--){
if(e[i].empty()){duan=i;break;}
u=e[i][e[i].size()-1];
vis[u]=1;
if(i==r)mx=u;
if(i==r||u==pre-1){pre=u;continue;}
if(pre==l&&u>=mx){duan=u;break;}
if(vis[u]){duan=i;break;}
return 0;
}
if(duan==-1||duan-l+1>r-duan)return 0;
for(int i=l;i<=r;i++)vis[i]=0;
for(int i=duan+1,len=duan-l+1;i<=r;i++){
if(e[i].empty()||(e[i][e[i].size()-1]!=(i-duan-1)%len+l))return 0;
e[i].pop_back();
}
return solve(l,duan)&&solve(duan+1,r);
}
#define ll long long
inline void work(){
n=read();m=read();
for(int i=1;i<=n;i++)e[i].clear();
int fl=0;
map<ll,bool>mp;
ll x;
for(int i=1,u,v;i<=m;i++){
u=read();v=read();
if(u==v)fl=1;
if(u>v)u^=v^=u^=v;
x=(ll)u*N+v;
if(mp[x])fl=1;
mp[x]=1;
e[v].push_back(u);
}
if(fl){puts("NO");return;}
for(int i=0;i<n;i++)sort(e[i].begin(),e[i].end(),greater<int>());
puts(solve(0,n-1)?"YES":"NO");
}
int main(){
int T=read();
while(T--)work();
return (0-0);
}