题意：将点放在两个集合，同一个集合的边保留，不同集合的边删去，使得边至少减少一半。
输出任何一种方案即可。如果不能，输出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[110][110];//two[i][j]=1表示i和j是一对捣蛋鬼 int n,m; int vis[110];//vis[i]=1表示i放入集合A中，=2表示i放在集合B中 int group[3];//group[1]统计A中的点的个数，group[2]统计B中的点的个数。int main() {int t,a,b;scanf("%d",&t);for(int q=1; q<=t; q++) {memset(vis,0,sizeof(vis));memset(group,0,sizeof(group));memset(two,0,sizeof(two));scanf("%d%d",&n,&m);for(int i=1; i<=m; i++) {scanf("%d%d",&a,&b);two[a][b]=two[b][a]=1;}int num=0;//每次取一个点插入到集合A或B中for(int i=1; i<=n; i++) {int tmp1=0,tmp2=0; //tmp1表示将点i放入到集合A中将产生多少条边，tmp2表示将点i放入到集合B中将产生多少条边for(int j=1; j<=n; j++) {if(vis[j]==1 && two[i][j]) {tmp1++;}if(vis[j]==2 && two[i][j]) {tmp2++;}}//放入哪个集合增加的边少，就将点i放入到哪个集合中if(tmp1>tmp2) {vis[i]=2;group[2]++;num+=tmp2;} else {vis[i]=1;group[1]++;num+=tmp1;}}if(num<=m/2) {printf("Case #%d: %d\n",q,group[1]);for(int i=1; i<=n; i++) {if(vis[i]==1)printf("%d ",i);}printf("\n");} else {printf("Case #%d: Impossible.\n",q);printf("\n");}}return 0; }