一、题面
二、分析
该题与之前做过的带权并查集的唯一区别就是数组开不下。所以需要用离散化的思想，只取那些有用的点来解决该问题。
离散化其实就是把这些所有用到的点收集后，去重，再排一下序，然后用新数组它们的下标代表他们。
接下来数组能开下了，就用带权并查集的做法去做，这里权值可以直接用bool值，然后随便写几个发现是异或关系。
但需要注意，这里还是需要将输入的坐标往左移一下，直接不去考虑同一个点的情况。
三、AC代码
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int MAXN = 1e4+2; 9 int par[MAXN], A[MAXN], B[MAXN];10 int Temp[MAXN], Cnt;11 bool Rank[MAXN], Odd[MAXN];12 13 void Init()14 {15 memset(par, -1, sizeof(par));16 memset(Rank, 0, sizeof(Rank));17 }18 19 int Pos(int x)20 {21 int left = 0, right = Cnt-1, mid;22 while(left <= right)23 {24 mid = (left+right)>>1;25 if(Temp[mid] == x)26 return mid;27 else if(Temp[mid] > x)28 right = mid-1;29 else30 left = mid+1;31 }32 return -1;33 }34 35 int Find(int x)36 {37 if(par[x] == -1) return x;38 int t = Find(par[x]);39 Rank[x] = Rank[x]^Rank[par[x]];40 return par[x] = t;41 }42 43 bool Union(int x, int y, bool flag)44 {45 int fx = Find(x);46 int fy = Find(y);47 if(fx == fy)48 {49 return (flag^Rank[y]) == Rank[x];50 }51 else52 {53 par[fx] = fy;54 Rank[fx] = flag^Rank[y]^Rank[x];55 return true;56 }57 }58 59 int main()60 {61 //freopen("input.txt", "r", stdin);62 int N, T, ans;63 char op[5];64 while(scanf("%d", &N)!=EOF)65 {66 Cnt = 0;67 Init();68 scanf("%d", &T);69 for(int i = 0; i < T; i++)70 {71 scanf("%d %d %s", &A[i], &B[i], op);72 A[i]--; //***73 Temp[Cnt++] = A[i];74 Temp[Cnt++] = B[i];75 Odd[i] = (op[0] == 'o');76 }77 sort(Temp, Temp + Cnt);78 Cnt = unique(Temp, Temp+Cnt) - Temp;79 int x, y;80 ans = T;81 82 for(int i = 0; i < T; i++)83 {84 x = Pos(A[i]);85 y = Pos(B[i]);86 if(!Union(x, y, Odd[i]))87 {88 ans = i;89 break;90 }91 }92 printf("%d\n", ans);93 }94 return 0;95 }