给定一张 \(n\) （保证 \(n\) 是 \(3\) 的倍数）个节点 \(m\) 条边的图，并且保证该图存在一个大小至少为 \(\frac{2}{3}n\) 的团。请输出该图的任意一个大小为 \(\frac{1}{3}n\)的团。

\(n\leq3000,\ m\leq n^2\)

贪心

---

神仙题一道……

结论：把所有不相邻的节点判掉，输出剩下的节点

若两点都不在团中，显然直接判掉；若其中一点在团中，判掉会失去一个答案节点。由于有至少 \(\frac{2}{3}n\) 个点两两相邻，因此最多只会执行 \(\frac{1}{3}n\) 次判点操作，于是就至少会留下 \(\frac{1}{3}n\) 个点，输出即可

时间复杂度 \(O(n^2)\)

代码

#include 
    
     using namespace std;const int maxn = 3010;int n, m, flg[maxn], a[maxn][maxn];int main() {  scanf("%d %d", &n, &m);  for (int i = 1; i <= m; i++) {    int u, v;    scanf("%d %d", &u, &v);    a[u][v] = a[v][u] = 1;  }  for (int i = 1; i <= n; i++) {    for (int j = i + 1; j <= n && !flg[i]; j++) {      if (!a[i][j] && !flg[j]) {        flg[i] = flg[j] = 1;      }    }  }  int cnt = 0;  for (int i = 1; i <= n; i++) {    if (!flg[i]) {      if (++cnt > n / 3) break;      printf("%d ", i);    }  }  return 0;}