Codeforce-1176E（二分图）

题意是最多选择 n/2 个点使得没有选中的点与选中的点相邻
cover it

思路

将一条线段的端点分成两部分，取其中一半就可以得到选中的点与没有选中的点相邻

#include<bits/stdc++.h>
using namespace std;
int vis[200010];
queue<int>qu1;
queue<int>qu2;
int main( )
{
    int t;
    cin>>t;
    while(t--)
    {
        while(!qu1.empty())
        {
              qu1.pop();
        }
        while(!qu2.empty())
        {
              qu2.pop();
        }
        int n,m;
        int x,y;
        cin>>n>>m;
        for(int i=1; i<=n; i++)
        {
            vis[i]=0;
        }
        for(int i=1; i<=m; i++)
        {
            cin>>x>>y;
            if(vis[x]==0&&vis[y]==0)
            {
                qu1.push(x);
                vis[x]=1;
                qu2.push(y);
                vis[y]=2;
            }
            if(vis[x]==1&&vis[y]==0)
            {
                qu2.push(y);
                vis[y]=2;
            }
            if(vis[x]==0&&vis[y]==1)
            {
                qu2.push(x);
                vis[x]=2;
            }
            if(vis[x]==0&&vis[y]==2)
            {
                qu1.push(x);
                vis[x]=1;
            }
            if(vis[x]==2&&vis[y]==0)
            {
                qu1.push(y);
                vis[y]=1;
            }

        }
        int len1=qu1.size( );
        int len2=qu2.size( );
        if(len1<=len2)
        {
            cout<<len1<<endl;
            while(!qu1.empty())
            {
                cout<<qu1.front()<<" ";
                qu1.pop();
            }
        }
        else
        {
            cout<<len2<<endl;
            while(!qu2.empty())
            {
                cout<<qu2.front()<<" ";
                qu2.pop( );
            }
        }
        cout<<endl;
    }

    return 0;
}