AcWing 239. 奇偶游戏
原题链接
中等
作者:
tire
,
2024-07-26 16:36:39
,
所有人可见
,
阅读 3
#include <cstdio>
#include <cstring>
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 2e4 + 10;
int n, m;
int p[N], d[N];
unordered_map<int, int> S;
int get(int x) {
if (S.count(x) == 0) {
S[x] = ++n;
}
return S[x];
}
int find(int x) {
if (p[x] != x) {
int root = find(p[x]);
d[x] = ( d[x] + d[p[x]]) % 2;
p[x] = root;
}
return p[x];
}
int main() {
cin >> n >> m;
n = 0;
for (int i = 0; i < N; i++) {
p[i] = i;
}
int res = m;
for (int i = 1; i <= m; i++) {
int a, b;
string type;
cin >> a >> b >> type;
a = get(a - 1), b = get(b); // s[a-1], s[b]
int t = 0;
if (type == "odd") {
t = 1;
}
int pa = find(a), pb = find(b);
if (pa == pb) {
if ((d[a] + d[b]) % 2 != t) {
res = i - 1;
break;
}
} else {
p[pa] = pb;
d[pa] = (d[a] + d[b] + t) % 2;
}
}
cout << res << endl;
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 2e4 + 10;
int n, m;
int p[N], d[N];
unordered_map<int, int> S;
int get(int x) {
if (S.count(x) == 0) {
S[x] = ++n;
}
return S[x];
}
int find(int x) {
if (p[x] != x) {
int root = find(p[x]);
d[x] ^= d[p[x]];
p[x] = root;
}
return p[x];
}
int main() {
cin >> n >> m;
n = 0;
for (int i = 0; i < N; i++) {
p[i] = i;
}
int res = m;
for (int i = 1; i <= m; i++) {
int a, b;
string type;
cin >> a >> b >> type;
a = get(a - 1), b = get(b); // s[a-1], s[b]
int t = 0;
if (type == "odd") {
t = 1;
}
int pa = find(a), pb = find(b);
if (pa == pb) {
if ((d[a] ^ d[b])!= t) {
res = i - 1;
break;
}
} else {
p[pa] = pb;
d[pa] = (d[a] ^ d[b] ^ t);
}
}
cout << res << endl;
}