【二分图+数据范围】牛客练习赛 E 奇环

小灰灰 2024-03-17 18:12 6阅读 0赞

题意:

![8617fc55e2924006b3c4bec0b0809d26.png][]

思路：

![8c82404c8ec6442693ffca2e0b62632b.png][]

Code:

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    
    struct ty{
        int to,next;
    }edge[mxe<<1];
    
    map<pair<int,int>,int > mp; 
    
    int N,M,u,v,tot=0;
    int head[mxn];
    int col[mxn];
    
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++){
            head[i]=-1;
        }
    }
    int dfs(int u,int c){
        col[u]=c;
        for(int i=head[u];~i;i=edge[i].next){
            if(col[edge[i].to]==-1){
                if(!dfs(edge[i].to,!c)) return false;
            }else if(col[edge[i].to]==c) return false;
        }
        return true;
    }
    void solve(){
        cin>>N>>M;
        G_init();
        mp.clear();
        for(int i=1;i<=M;i++){
            cin>>u>>v;
            mp[{u,v}]=mp[{v,u}]=1;
        }
        if(N>=896||N*N/4-N/2-100>M){
            cout<<"YES"<<'\n';
            return;
        }
        for(int i=1;i<=N;i++){
            for(int j=i+1;j<=N;j++){
                if(!mp.count({i,j})&&!mp.count({j,i})){
                    add(i,j);
                    add(j,i);
                }
            }
        }
        memset(col,-1,sizeof(col));
        for(int i=1;i<=N;i++){
            if(col[i]==-1){
                if(!dfs(i,0)){
                    cout<<"YES"<<'\n';
                    return;
                }
            }
        }
        cout<<"NO"<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[8617fc55e2924006b3c4bec0b0809d26.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/3366ca8ed69e4e0dbcc22585c1d39c68.png
[8c82404c8ec6442693ffca2e0b62632b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/f0f9661731bd45b4811555add61b58f1.png