POJ 1733 Parity game——并查集 + 离散化

POJ 1733 Parity game——并查集 + 离散化

#include #include using namespace std;const int maxn = 1e4 + 10;int T, N, M, par[maxn], val[maxn], a[maxn];struct Date { char str[10]; int x, y;}date[maxn];int Query(int x) { if (x != par[x]) { int temp = par[x]; par[x] = Query(par[x]); val[x] = val[x] ^ val[temp]; } return par[x];}int main() { while (~scanf("%d %d", &N, &M)) { int cnt = 0; for (int i = 1; i <= M; i++) { scanf("%d%d%s", &date[i].x, &date[i].y, date[i].str); date[i].x--; a[++cnt] = date[i].x; a[++cnt] = date[i].y; } sort(a + 1, a + 1 + cnt); cnt = unique(a + 1, a + 1 + cnt) - a; for (int i = 1; i <= cnt; i++) par[i] = i, val[i] = 0; int ans = 0; for (int i = 1; i <= M; i++) { int x = lower_bound(a + 1, a + 1 + cnt, date[i].x) - a; int y = lower_bound(a + 1, a + 1 + cnt, date[i].y) - a; int a = Query(x), b = Query(y); if (a == b) { if ((val[x] ^ val[y]) % 2 == 0 && date[i].str[0] == 'o') break; if ((val[x] ^ val[y]) % 2 == 1 && date[i].str[0] == 'e') break; ans++; } else { if (date[i].str[0] == 'o') { par[a] = b; val[a] = val[x] ^ val[y] ^ 1; } else { par[a] = b; val[a] = val[x] ^ val[y]; } ans++; } } printf("%d\n", ans); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。