并查集找冗余的边

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;
int n, m, r, c;
char d; // d == directions

// Path Compression
int Find(vector<int>&p, int x) {
  return p[x] ^ x ? p[x] = Find(p, p[x]) : x;
}

bool Union(vector<int>&p, int u, int v) {
  const int pu = Find(p, u);
  const int pv = Find(p, v);
  if (pu == pv) return false; // 有环 （redundant edge）
  p[pu] = pv;
  return true;
}

int main(void) {
  scanf("%d %d", &n, &m);
  vector<int> p(n * n);
  iota(begin(p), end(p), 0);

  for (int i = 1; i <= m; ++i) {
    scanf("%d %d %c", &r, &c, &d);
    int r2, c2;
    if (d == 'D') r2 = r + 1, c2 = c;
    else r2 = r, c2 = c + 1;

    // 降维操作: 二维坐标转一维坐标
    if (!Union(p, (r - 1) * n + c - 1, (r2 - 1) * n + c2 - 1)) // zero-based
      return printf("%d\n", i), 0;
  }
  return puts("draw"), 0;
}