nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老blog

镜像并查集

镜像处理时都有这种关系
朋友的朋友是朋友,敌人的敌人是朋友,朋友的敌人是敌人,敌人的朋友是朋友,

如何快速判断朋友与敌人呢?
我们让每个人都有两重身份,一个是自己,一个是自己的相反面,即a与a'是天生的敌人,b与b'是天生的敌人
当a和b成为朋友的时候,我们让a'与b'成为朋友,a与b',b与a'成为敌人
当a和b成为敌人的时候,我们让a'与b'成为敌人,a与b',b与a'成为朋友
如此我们就可以迅速判断多组输入时候的朋友与敌人关系了

例如1与2是敌人,2与3是敌人,3与4是敌人,4与5是敌人
   问1与5什么关系
   我们来建立模型
       1与2是敌人 [1,  2']. [1',  2]
       2与3是敌人[1,  2',  3]. [1',  2,  3']
       3与4是敌人[1,  2',  3,  4']. [1',  2,  3',  4]
       4与5是敌人[1,  2',  3,  4',  5]. [1',  2,  3',  4,  5']
       以经很明显了1和5是朋友

1.判断一个图是否是二分图
把每个点分成两个点,一个代表本身,一个代表对立面(镜像),对每条边(u,v)都使用join(u+n,v),join(u,n+v)
最后判断find(1)==find(n+1)?相等则不是二分图,反之为二分图