小问题
查看原帖
小问题
416242
New_hope楼主2023/12/23 10:40

以下是已经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);

时,就只有 40pts40 \text{pts}。

所以为啥不是记录 xx 最后被赋值的 yy 的下标,而是 yy 的来源?

2023/12/23 10:40
加载中...