原题：
Description
有n个人，编号为1àn，告诉你那些人之间是不友好的。现在，让你将这n个人分成两组，使得每一组之内的人是互相友好的，如果可以分成两组，则输出如何分组的，如果不可以分成两组，那么，输出“IMPOSSIBLE”。
Input
第一行两个整数n和m，1<=n<=50000，0<=m<=500000，分别表示人数以及不友好的人的对数。以下m行每行两个数a，b，表示a与b是不友好的。
Output
如果可以分成两个组，则输出一个方案，第一行为第一组的人的编号，第二行为第二组人的，按升序输出。其中，方案的字典序必须要最小，所谓的方案字典序最小，就是第一行和第二行连接，组成的序列的字典序最小，如果有多种分配方法，取第一个组别人数最多的方案。如果不能分成两组，输出“IMPOSSIBLE”。
Sample Input（relation.in）
5 4
1 4
1 5
2 4
2 5
Sample Output（relation.out）
1 2 3
4 5
样例解释：
有两种方案，1 2 3 和 1 2
4 5 3 4 5
两种方案的字典序相同，取第一组人数最多的方案，所以输出方案一。
题目满足：
40%的数据n<=1000
100%的数据n<=50000，m<=500000
时限 1s
这道题典型的二分图染色（因为分成2组）
当然，根据题目，我们最后要SORT一下输出
并且，方案字典序相同时，取第一组人数最多的方案
所以染色的时候尽量多分配1，不行再回溯修改
下面贴代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct edge{ int to,next; }g[1000001]; int color[50001]; int head[50001],n,m; bool visit[50001]; int ans1[50001],ans2[50001],num=0,num1=0,num2=0; void ins(int x,int y){g[++num].next=head[x];head[x]=num;g[num].to=y;} void insw(int x,int y){ins(x,y);ins(y,x);} bool dfs(int x){ visit[x]=true; for(int i=head[x];i;i=g[i].next) { if(!visit[g[i].to]) { color[g[i].to]=color[x]==1?0:1; visit[g[i].to]=true; if(!dfs(g[i].to))color[x]=color[x]==1?0:1; } else if(color[g[i].to]!=-1&&color[g[i].to]==color[x]){color[x]=color[x]==1?0:1;return false;} } return true; } int main(){ freopen("relation.in","r",stdin); freopen("relation.out","w",stdout); memset(color,-1,sizeof(color)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); insw(x,y); } bool shuchu=false; for(int i=1;i<=n;i++) { if(color[i]==-1){color[i]=1;if(!dfs(i)){printf("IMPOSSIBLE ");shuchu=true;break;}} } if(!shuchu){ for(int i=1;i<=n;i++) if(color[i]||color[i]==-1)ans1[++num1]=i; else ans2[++num2]=i; sort(ans1+1,ans1+num1+1); sort(ans2+1,ans2+num2+1); for(int i=1;i<num1;i++) printf("%d ",ans1[i]); printf("%d ",ans1[num1]); for(int i=1;i<num2;i++) printf("%d ",ans2[i]); printf("%d ",ans2[num2]); } fclose(stdin); fclose(stdout); }