以下是已经AC的代码
#include<bits/stdc++.h>
#define _ (int)(1e5 + 4)
using namespace std;
int c, t;
int n, m;
int v[_], p[_ << 2];
/*
v[i] : 最后给i赋值的下标和状态
p[i] : i = F, p[i+n] : i = T
*/
int find(int x) {
if(p[x] == x) return x;
else return p[x] = find(p[x]);
}
void merge(int x, int y) {
p[find(x)] = find(y);
}
void solve() {
cin >> n >> m;
for(int i = 1; i <= n; i ++) v[i] = i;
for(int i = 1; i <= m; i ++) {
char c; int x, y;
cin >> c;
if(c == '+' || c == '-') {
cin >> x >> y;
v[x] = (c == '+' ? v[y] : -v[y]);
}
else {
cin >> x;
v[x] = (c == 'U' ? _ + 1 : _ + 2);
}
}
for(int i = 1; i <= 2*n; i ++) p[i] = i;
for(int i = 1; i <= n; i ++) {
if(abs(v[i]) == _ + 2) continue;
if(abs(v[i]) == _ + 1) p[find(i)] = find(i + n);
else if(v[i] < 0) {
merge(i, -v[i] + n);
merge(i + n, -v[i]);
}
else {
merge(i, v[i]);
merge(i + n, v[i] + n);
}
}
int r = 0;
for(int i = 1; i <= n; i ++) {
if(find(i) == find(i + n)) r ++;
}
cout << r << endl;
}
int main() {
cin >> c >> t;
while(t --) solve();
return 0;
}
/*
1 3
2 2
T 2
U 2
*/
但是当这行代码:
v[x] = (c == '+' ? v[y] : -v[y]);
改为:
v[x] = (c == '+' ? y : -y);
时,就只有 40pts。
所以为啥不是记录 x 最后被赋值的 y 的下标,而是 y 的来源?