POJ1733 Parity game ——种类并查集+离散化

admin管理员组

文章数量:1597395

POJ1733

题意：

有n个结点，给出了q个操作，操作是a b string表示结点a到结点b的和是奇数或偶数，输出x(前x个操作都是正确的)。

思路 ：

用种类并查集就可以啦...不过要注意三点, 一是数据范围1e9, 不能直接用做数组下标, 要先离散化一下; 二是输入的数据中x, y是闭区间, 不好处理, 我们可以将其化为半开区间来处理, (x-1, y] 或者 [x, y+1)

全部正确输出m

// Decline is inevitable,
// Romance will last forever.
// POJ1733
//#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <vector>
using namespace std;
#define mst(a, x) memset(a, x, sizeof(a))
#define INF 0x3f3f3f3f
//#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
//#define int long long
const int maxn = 1e4 + 10;
const int maxm = 25;
const int P = 1e9 + 7;
int fa[maxn];
int n, m;
int re[maxn];   //0表示到父节点是偶数 1表示奇数
int find(int x) {
    if(x == fa[x]) return x;
    int tmp = fa[x];
    fa[x] = find(fa[x]);
    re[x] = (re[tmp] + re[x]) % 2;
    return fa[x];
}
map<int, int> mp;
void solve() {
    cin >> n >> m;
    for(int i = 0; i <= maxn; i++) {
        fa[i] = i;
        re[i] = 0;
    }
    int cnt = 1;
    for(int j = 1; j <= m; j++){
        int x, y;
        int d = 0;
        char c[10];
        scanf("%d%d%s", &x,&y,c);
        if(!mp[x-1]) mp[x-1] = cnt++;
        if(!mp[y]) mp[y] = cnt++;
        if(c[0] == 'o') d++;
        int fx = find(mp[x-1]);
        int fy = find(mp[y]);
        if(fx != fy) {
            fa[fx] = fy;
            re[fx] = (re[mp[x-1]] + re[mp[y]] + d) % 2;
            continue;
        }
        if(fx == fy) {
            if((re[mp[x-1]] ^ re[mp[y]]) != d) {
                printf("%d\n", j-1);
                return;
            }
        }
    }
    printf("%d\n", m);
}
signed main() {
//    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int T; scanf("%d", &T); while(T--)
//    int T; cin >> T; while(T--)
    solve();
    return 0;
}

本文标签： 种类Paritygame