P5937. Parity Game

发表于 2023-11-13 分类于洛谷阅读次数： Waline：本文字数： 492 阅读时长 ≈ 2 分钟

考点

边带权并查集

题解

#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e5 + 50;
int n, m, cnt, fa[LEN], val[LEN], discrete[LEN];

struct node {
  int x_, y_, w_;
} arr[LEN];

int find(int x) {
  if (fa[x] == x) return x;
  int anc = fa[x];
  fa[x] = find(fa[x]);
  val[x] ^= val[anc];
  return fa[x];
}

void join(int x, int y, int w) {
  int a = find(x), b = find(y);
  val[a] = w ^ val[y] ^ val[x];
  fa[a] = b;
}

void init() {
  // 离散化开始
  sort(discrete + 1, discrete + 1 + cnt);
  cnt = unique(discrete + 1, discrete + 1 + cnt) - (discrete + 1);
  for (int i = 1; i <= m; ++i) {
    arr[i].x_ =
        lower_bound(discrete + 1, discrete + 1 + cnt, arr[i].x_) - discrete;
    arr[i].y_ =
        lower_bound(discrete + 1, discrete + 1 + cnt, arr[i].y_) - discrete;
  }
  // 离散化结束
  for (int i = 0; i <= cnt; ++i) fa[i] = i;
}

void work() {
  int x, y, w;
  for (int i = 1; i <= m; ++i) {
    x = arr[i].x_, y = arr[i].y_, w = arr[i].w_;
    --x;
    if (find(x) != find(y)) {
      join(x, y, w);
    } else {
      if (val[x] ^ val[y] != w) {
        cout << i - 1 << endl;
        return;
      }
    }
  }
  cout << m << endl;
}

int main() {
  string str;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> arr[i].x_ >> arr[i].y_ >> str;
    arr[i].w_ = str[0] == 'e' ? 0 : 1;
    discrete[++cnt] = arr[i].x_, discrete[++cnt] = arr[i].y_;
  }
  init(), work();
  return 0;
}