poj 1733 Parity game

点击打开链接 poj 1733

1思路： 带权并查集+map+离散化思想
2分析： 由于n的值达到1000000000.所以如果还是直接用原来的方法的话肯定是不行的，所以想到了离散化思想。这里可以用map和hash离散，其它跟带权并查集一样的思路。
3注意： 这一题只有一个case，然后只要好到了ans后就直接break如果是用continue就会WA。还有如果如初结束没找到ans就输出k值。

4代码：

map版

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define MAXN 10010

int n , k , ans , cnt;
int father[MAXN];
int rank[MAXN];
map<int , int>m;

/*并查集的初始化*/
void init_Set(){
    m.clear();
    ans = cnt = 0;
    for(int i = 0 ; i <= MAXN ; i++){
       father[i] = i;
       rank[i] = 0;
    }
}

/*并查集的查找*/
int find_Set(int x){
    if(father[x] == x)
       return x;
    int tmp = father[x];
    father[x] = find_Set(tmp);
    rank[x] += rank[tmp];
    rank[x] %= 2;/*要mod 2*/
    return father[x];
}

/*并查集的合并*/
void union_Set(int x , int y , int m){
     int root_x = find_Set(x);
     int root_y = find_Set(y);
     father[root_y] = root_x;
     rank[root_y] = (rank[x]-rank[y]+m+2)%2;/*注意只要有出现相减的地方要先加上2在mod 2，保证结果正确*/
}

int main(){
    int left , right;
    char ch[15];
    map<int ,int>::iterator it;
    scanf("%d%d" , &n , &k);
    init_Set();
    for(int i = 0  ; i < k ; i++){
         scanf("%d%d%s" , &left , &right , ch);
         left--;
         it = m.find(left);
         if(it == m.end())
            m[left] = cnt++;
         it = m.find(right);
         if(it == m.end())
             m[right] = cnt++;
         if(!strcmp(ch , "even")){ 
             if(find_Set(m[left])  == find_Set(m[right])){
                 if((rank[m[right]]-rank[m[left]]+2)%2 != 0 && !ans){/*要加上2再mod2*/
                   ans = i+1;
                   break;
                  }
               }
               else
                   union_Set(m[left] , m[right] , 0);/*合并*/
            }
          else{
              if(find_Set(m[left]) == find_Set(m[right])){
                 if((rank[m[right]]-rank[m[left]]+2)%2 != 1 && !ans){/*要先加2再mod 2*/
                   ans = i+1;
                   break;
                 }
              }
              else
                  union_Set(m[left] , m[right] , 1);/*合并*/
         }
     }
     if(ans)
        printf("%d\n" , ans-1);
     else
        printf("%d\n" , k);
    return 0;
}

hash版

/*
 思路：hash + 带权并查集 + 离散化
 分析：n非常大，所以必须使用离散化。这里就用到了hash表，把当前的点映射到另外一个整数，通过这个整数来查找和合并并查集。
 
 hash表的使用：用一个first数组来表示表头，由于hash值会有重复所以要用一个next数组来表示链表。first[i]表示的是hash值为i的点的映射值，next[i]表示映射值为i的点的下一个有关系的点的映射值（和邻接表一样），num[i]表示映射值为i的点的原来的值。
               这里的hash值求解选择取于法。
 */

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 10003

int ans , n , m , cnt;
int first[MAXN];
int next[MAXN];
int father[MAXN];
int rank[MAXN];
int num[MAXN];

/*判断是否插入成功*/
int hash_insert(int x){
    int h = x%MAXN;/*求出hash值为h*/
    int u = first[h];
    while(u != -1){
        if(num[u] == x)/*如果在hash表中直接返回映射值u*/
            return u;
        u = next[u];
    }
    cnt++;
    num[cnt] = x;/*cnt作为点x的映射值*/
    next[cnt] = first[h];/*表头往后移动*/
    first[h] = cnt;/*更新表头*/
    return cnt;
}

/*并查集的初始化*/
void init_Set(){
    ans = cnt = 0;
    memset(first , -1 , sizeof(first));
    memset(next , -1 , sizeof(next));
    memset(num , -1 , sizeof(num));
    for(int i = 0 ; i <= MAXN ; i++){
       father[i] = i;
       rank[i] = 0;
    }
}

/*并查集的查找*/
int find_Set(int x){
    if(father[x] == x)
        return x;
    int tmp = father[x];
    father[x] = find_Set(tmp);
    rank[x] = (rank[x]+rank[tmp])%2;
    return father[x];
}

/*并查集的合并*/
void union_Set(int x , int y , int m){
    int root_x = find_Set(x);
    int root_y = find_Set(y);
    father[root_y] = root_x;
    rank[root_y] = (rank[x]+m-rank[y]+2)%2;
}

int main(){
    char ch[15];
    int left , right;
    scanf("%d%d" , &n , &m);
    init_Set();
    for(int i = 0 ; i < m ; i++){
       scanf("%d%d%s" , &left , &right , ch);
       int a = hash_insert(left-1);
       int b = hash_insert(right);
       if(!strcmp(ch , "even")){
           if(find_Set(a) == find_Set(b)){
              if((rank[b]-rank[a]+2)%2 != 0 && !ans){
                 ans = i+1;
                 break;
              }
           }
           else
               union_Set(a , b , 0);
       }
       else{
           if(find_Set(a) == find_Set(b)){
              if((rank[b]-rank[a]+2)%2 != 1 && !ans){
                  ans = i+1;
                  break;
              }
           }
           union_Set(a , b , 1);
       }
    }
    if(ans)
        printf("%d\n" , ans-1);
    else
        printf("%d\n" , m);
    return 0;
}