题意

思路

权值并查集

#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 10;
int n, m;
unordered_map<int, int> mp;
int f[N], d[N];int get(int x)
{if (mp.count(x) == 0) mp[x] = ++ n;return mp[x];
}int find(int x)
{if (f[x] != x){int root = find(f[x]);d[x] += d[f[x]];f[x] = root;}return f[x];
}int main()
{scanf("%d %d", &n, &m);n = 0;for (int i = 1; i < N; i ++) f[i] = i;int res = m;int x, y; char type[10];for (int i = 1; i <= m; i ++) {scanf("%d %d %s", &x, &y, type);x = get(x - 1), y = get(y);int fx = find(x), fy = find(y);int t = 0;if (type[0] == 'o') t = 1;if (fx == fy){if (((d[x] + d[y]) % 2 + 2) % 2 != t){res = i - 1;break;}}else{f[fx] = fy;d[fx] = d[x] ^ d[y] ^ t;}}printf("%d\n", res);return 0;
}

种类并查集

#include <bits/stdc++.h>
using namespace std;const int N = 2e4 + 10;
int n, m;
int f[N];
unordered_map<int, int> mp;int get(int x)
{if (mp.count(x) == 0) mp[x] = ++ n;return mp[x];
}int find(int x)
{if (f[x] != x) f[x] = find(f[x]);       return f[x];                        //这里必须返回 f[x] ,  对于这种递归方式
}int main()
{scanf("%d %d", &n, &m);n = 0;for (int i = 1; i < N; i ++) f[i] = i;int x, y; char type[10];int res = m;for (int i = 1; i <= m; i ++) {scanf("%d %d %s", &x, &y, type);x = get(x - 1), y = get(y);if (type[0] == 'e'){if (find(x + N / 2) == find(y)){res = i - 1;break;}f[find(x)] = find(y);f[find(x + N / 2)] = find(y + N / 2);}else{if (find(x) == find(y)){res = i - 1;break;}f[find(x)] = find(y + N / 2);f[find(y)] = find(x + N / 2);}}printf("%d\n", res);return 0;
}