BZOJ 2530 Poi 2011 Party【列挙】

BZOJ 2530 Poi2011 Party
Description
Byteasar intends to throw up a party. Naturally, he would like it to be a success. Furthermore, Byteasar is quite certain that to make it so it suffices if all invited guests know each other. He is currently trying to come up with a list of his friends he would like to invite. Byteasar has friends, where is divisible by 3. Fortunately, most of Byteasar’s friends know one another. Furthermore, Byteasar recalls that he once attended a party where there were2/3 n of his friends, and where everyone knew everyone else. Unfortunately, Byteasar does not quite remember anything else from that party… In particular, he has no idea which of his friends attended it. Byteasar does not feel obliged to throw a huge party, but he would like to invite at least n/3of his friends. He has no idea how to choose them, so he asks you for help. Nを1枚与える(Nが3の倍数であることを保証する)個のノードMの辺の図であり、かつ図に少なくとも2 N/3の大きさの団があることを保証する.図のいずれかの大きさN/3の団を出力してください.一つの団の定義はノードのサブセットであり、このサブセットの点は2つの直接の辺である.入力:第1行は2つの整数N,Mである.次にM行があり、各行は2つの整数A,Bであり、AとBは縁つなぎ重さがないことを保証します.出力:N/3個の整数で、あなたが見つけた団を表します.データ範囲:3<=N<=3000,[3/2 n(2/3 n-1)]/2<=M<=[n(n-1)/2]
Input
In the first line of the standard input two integers, n and M(3<=N<=3000,[3/2 n(2/3 n -1)]/2<=M<=[n(n-1)/2]), are given, separated by a single space. These denote the number of Byteasar’s friends and the number of pairs of his friends who know each other, respectively. Byteasar’s friends are numbered from 1 to . Each of the following lines holds two integers separated by a single space. The numbers in line no.i+1(for i=1,2,…,m) are Ai and Bi(1<=Ai
Output
In the first and only line of the standard output your program should print N/3numbers, separated by single spaces, in increasing order. These number should specify the numbers of Byteasar’s friends whom he should invite to the party. As there are multiple solutions, pick one arbitrarily.
Sample Input
6 10 2 5 1 4 1 5 2 4 1 3 4 5 4 6 3 5 3 4 3 6
Sample Output
2 4
HINT
Explanation of the example: Byteasar’s friends numbered 1, 3, 4, 5 know one another. However, any pair of Byteasar’s friends who know each other, like 2 and 4 for instance, constitutes a correct solution, i.e., such a pair needs not be part of aforementioned quadruple.
まず任意の2つの点の間に縁がなければ、この2つの点を削除します.団の中にいない点は最大n 3frac{n}{3}3 nで、毎回2つの点を削除します.団内の点も最大n 3frac{n}{3}3 nで、少なくともn 3frac{n}{3}3 n個の団内の点が残っているので最後に削除されていない点の中からn 3frac{n}{3}3 n個をそのまま取るとよい

#include
using namespace std;
#define fu(a,b,c) for(int a=b;a<=c;++a)
#define N 3010
int n,m;
bool vis[N],g[N][N];
int main(){
  scanf("%d%d",&n,&m); 
  fu(i,1,m){
    int x,y;
    scanf("%d%d",&x,&y);
    g[x][y]=1;
  }
  fu(i,1,n)if(!vis[i])
    fu(j,i+1,n)if(!vis[j])
      if(!g[i][j]){vis[i]=vis[j]=1;break;}
  int siz=0;
  fu(i,1,n)if(!vis[i]&&siz<n/3)printf("%d ",i),siz++;
}