POJ 1733 Parity game

题目链接~~>

做题感悟：做完这题第一感觉就是并查集的题只要一加深一下就不会了。

解题思路：

              给你长度为 n 的 0 和 1 组成的字符串，然后问给你许多条件  x ~ y 之间（包括x , y ）有奇数个 1 或偶数个 1 ，基于以前的条件判断是否正确（只要存在一种情况正确就可以）.首先对于 x ~ y 如果你知道 x~z 的奇偶性（即 1 的个数的奇偶性）同时知道 y~z 的奇偶性，从而就可以判断  x~y 的奇偶性。

             例如：x ~ z 为偶数个（用 0 表示），y ~  z 为奇数个（用 1 表示），那么x ~ y 必定奇数个。这样可以用异或来表示： T[x].relation ^ T[y].relation .

             判断时：如果 find( x )  = =  find( y )  只要异或一下看是否等于输入的奇偶性就可以了。 否则，合并 x  y 所在集合。

因为 n 很大开数组开不下，而m可以开的下，so 用map 离散化。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const double PI = 3.1415926 ;
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const int MX =100006 ;
     
    
   

    

     

    
    

     

      int n,mx ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int parent,relation ;
     
    
   

    

     

    
    

     

      }T[MX] ;
     
    
   

    

     

    
    

     

      void init() // 初始化
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i=0 ;i<MX ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       T[i].parent=i ;
     
    
   

    

     

    
    

     

       T[i].relation=0 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int find(int x) // 寻找父亲 同时更新节点信息
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(T[x].parent!=x)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int temp=T[x].parent ;
     
    
   

    

     

    
    

     

       T[x].parent=find(temp) ;
     
    
   

    

     

    
    

     

       T[x].relation=T[x].relation^T[temp].relation ;
     
    
   

    

     

    
    

     
 return T[x].parent ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return T[x].parent ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x,y,r=0,i,c ;
     
    
   

    

     

    
    

     
 char s[20] ;
     
    
   

    

     

    
    

     
 map<int,int>m ;
     
    
   

    

     

    
    

     
 scanf("%d%d",&n,&mx) ;
     
    
   

    

     

    
    

     

       init() ;
     
    
   

    

     

    
    

     
 for(i=1 ;i<=mx ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d%s",&x,&y,s) ;
     
    
   

    

     

    
    

     
 if(s[0]=='e')
     
    
   

    

     

    
    

     

       c=0 ;
     
    
   

    

     

    
    

     
 else c=1 ;
     
    
   

    

     

    
    

     

       x-- ;
     
    
   

    

     

    
    

     
 if(m.find(x)==m.end()) // 因为 n 很大 so 用map离散化
     
    
   

    

     

    
    

     

       m[x]=r++ ;
     
    
   

    

     

    
    

     
 if(m.find(y)==m.end())
     
    
   

    

     

    
    

     

       m[y]=r++ ;
     
    
   

    

     

    
    

     

       x=m[x] ;
     
    
   

    

     

    
    

     

       y=m[y] ;
     
    
   

    

     

    
    

     
 int ax=find(x) ; // 寻找父亲
     
    
   

    

     

    
    

     
 int ay=find(y) ;
     
    
   

    

     

    
    

     
 if(ax==ay) // 父亲相同
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if((T[x].relation^T[y].relation)!=c)
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       T[ay].parent=ax ;
     
    
   

    

     

    
    

     

       T[ay].relation=T[x].relation^T[y].relation^c ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%d\n",i-1) ;
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/22513325