Relation(Path集-改变father后必须进行dis维护)
Relation（relation.pas/.cpp）
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
Path集可做。。。事后发现二分图染色都行。。。。
不说什么了、、、（下次注意多看几遍）
本题要注意一个结点改变father后要当场维护dis。。。
要是漏的话就糟糕了。。。
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#include<functional>#include<cmath>#include<cctype>#include<cassert>#include<climits>using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Rep(i,n) for(int i=0;i<n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define ForD(i,n) for(int i=n;i;i--)#define Forp(x) for(int p=pre[x];p;p=next[p])#define RepD(i,n) for(int i=n;i>=0;i--)#define MEM(a) memset(a,0,sizeof(a))#define MEMI(a) memset(a,127,sizeof(a))#define MEMi(a) memset(a,128,sizeof(a))#define INF (2139062143)#define F (1000000009)#define MAXN (50000+10)#define MAXM (500000+10)typedef long long ll;int father[MAXN]={0},dis[MAXN]={0},n,m;int getfather(int x){ if (father[x]==x) return x; int q_father=father[x]; father[x]=getfather(father[x]); dis[x]=(dis[x]^dis[q_father])&1; return father[x];}void union2(int x,int y){ int i=getfather(x),j=getfather(y); if(i<j) swap(i,j); father[i]=j; dis[i]=((dis[x]^dis[y])&1)^1; }int color[MAXN]={0};int main(){ freopen("relation.in","r",stdin); freopen("relation.out","w",stdout); scanf("%d%d",&n,&m); For(i,n) father[i]=i; For(i,m) { int x,y; scanf("%d%d",&x,&y); if (getfather(x)^getfather(y)) union2(x,y); else { if (dis[x]==dis[y]) { puts("IMPOSSIBLE"); return 0; } } } For(i,n) getfather(i); //不能用father[x]=getfather(father[x]); /**/// For(i,10) cout<<father[i]<<' '<<dis[i]<<endl; /**/ int tot2=0; For(i,n) { if (father[i]==i) color[i]=2; else color[i]=color[father[i]]^dis[i]; if (color[i]==2) tot2++; } int tot3=n-tot2; bool b=0; For(i,n) if (color[i]==2){if (b) printf(" %d",i);else printf("%d",i),b=1;} puts(""); b=0; For(i,n) if (color[i]==3){if (b) printf(" %d",i);else printf("%d",i),b=1;} puts(""); // while(1); return 0;}