【POJ1733】Parity game

题面

vjudge

题解

比较简单的分类并查集

将一个查询操作看作前缀和\(s_r-s_{l-1}\)的奇偶性

将每个点拆成一奇一偶然后分别连边即可

如果一个点的奇点和偶点被连在一起了就判无解即可

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <climits>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();

    if (ch == '-') w = -1 , ch = getchar();

    while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();

    return w * data;

}

const int MAX_N = 5005;

int M, N, l[MAX_N], r[MAX_N], X[MAX_N << 1], cnt;

int fa[MAX_N << 1];

int getf(int x) { return (x == fa[x]) ? x : (x = getf(fa[x])); }

void unite(int x, int y) { fa[getf(x)] = getf(y); }

bool same(int x, int y) { return getf(x) == getf(y); }

char ch[MAX_N][10];

int main () {

	M = gi(), N = gi();

	for (int i = 1; i <= N; i++) {

		l[i] = gi() - 1, r[i] = gi();

		X[++cnt] = l[i], X[++cnt] = r[i];

		scanf("%s", ch[i]);

	}

	sort(&X[1], &X[cnt + 1]); cnt = unique(&X[1], &X[cnt + 1]) - X - 1;

	for (int i = 1; i <= N; i++) {

		l[i] = lower_bound(&X[1], &X[cnt + 1], l[i]) - X;

		r[i] = lower_bound(&X[1], &X[cnt + 1], r[i]) - X;

	}

	for (int i = 1; i <= N * 2; i++) fa[i] = i;

	for (int i = 1; i <= N; i++) {

		char op = ch[i][0]; int x = l[i], y = r[i];

		if (op == 'e') {

			unite(x, y); unite(x + N, y + N);

			if (same(x + N, x) || same(y, y + N)) return printf("%d\n", i - 1) & 0;

		} else {

			unite(x, y + N); unite(x + N, y);

			if (same(x + N, x) || same(y, y + N)) return printf("%d\n", i - 1) & 0;

		}

	}

	printf("%d\n", N);

    return 0;

}