题意：将点放在两个集合，同一个集合的边保留，不同集合的边删去，使得边至少减少一半。
输出任何一种方案即可。如果不能，输出Impossible
思路：设如果两个人为一对捣蛋鬼，则two[i][j]=two[j][i]=1，即用边表示关系
刚开始设集合为A、B，为空集。然后每次取一个点，往集合里加，加入到哪个集合使得增加的边最少就加入到那个集合中。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std; int two[][];//two[i][j]=1表示i和j是一对捣蛋鬼
int n,m;
int vis[];//vis[i]=1表示i放入集合A中，=2表示i放在集合B中
int group[];//group[1]统计A中的点的个数，group[2]统计B中的点的个数。 int main() {
int t,a,b;
scanf("%d",&t);
for(int q=; q<=t; q++) {
memset(vis,,sizeof(vis));
memset(group,,sizeof(group));
memset(two,,sizeof(two));
scanf("%d%d",&n,&m);
for(int i=; i<=m; i++) {
scanf("%d%d",&a,&b);
two[a][b]=two[b][a]=;
}
int num=;
//每次取一个点插入到集合A或B中
for(int i=; i<=n; i++) {
int tmp1=,tmp2=; //tmp1表示将点i放入到集合A中将产生多少条边，tmp2表示将点i放入到集合B中将产生多少条边
for(int j=; j<=n; j++) {
if(vis[j]== && two[i][j]) {
tmp1++;
}
if(vis[j]== && two[i][j]) {
tmp2++;
}
}
//放入哪个集合增加的边少，就将点i放入到哪个集合中
if(tmp1>tmp2) {
vis[i]=;
group[]++;
num+=tmp2;
} else {
vis[i]=;
group[]++;
num+=tmp1;
}
}
if(num<=m/) {
printf("Case #%d: %d\n",q,group[]);
for(int i=; i<=n; i++) {
if(vis[i]==)
printf("%d ",i);
}
printf("\n");
} else {
printf("Case #%d: Impossible.\n",q);
printf("\n");
}
}
return ;
}