Luogu

分析

团相当于一个完全子图。

于是枚举两个点,如果它们之间没有连边就给这两个点打一个标记。

注意这里打完标记后要 break ,因为此时这个点已经不可能在团中了。

这样子每个不在团中的点最多标记掉一个在团中的点,于是至少剩下 $\frac{1}{3}n$ 个点。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=3000+10;

int G[N][N],mark[N];

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        G[u][v]=G[v][u]=1;
    }
    for (re int i=1;i<=n;++i) {
        if (mark[i]) continue;
        for (re int j=i+1;j<=n;++j) {
            if (mark[j]) continue;
            if (!G[i][j]&&!G[j][i]) { mark[i]=mark[j]=1; break; }
        }
    }
    for (re int i=1,s=0;i<=n;++i) {
        if (mark[i]) continue;
        printf("%d ",i),++s;
        if (s==n/3) break;
    }
    return 0;
}
最后修改:2019 年 06 月 28 日 03 : 22 PM