ZOJ_3261_逆并查集

ZOJ 3261 逆并查集

  • 思路简单代码繁琐一直wa调了一天，真的菜
  • 因为并查集没有摧毁边的操作,那我们不妨先合并所有边中 不会被摧毁的边,那么就需要我们先保存所有的边,(这里太繁琐容易出错)
  • 开一个数组记录每个点的值,因为要找值最大 或者 值相同但点最小的点,在合并的时候根据这个来合并,值小的指向值大的,(值相同时,大点指向小点)
  • 这里用了一个技巧就是 map<pair<int,int> , int> 除去被摧毁的边,然后从遍历map合并边.
    坑点
  1. 注意存边的数组大小,
  2. 初始化和清除map,
  3. 每组数据输出一个空行
  4. merge(a,b)时保证a<b,这样merge()规定的顺序才有意义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <string.h>
#include <map>
#include <string>

using namespace std;

const int maxn = 1e4+5;
int pre[maxn];
int rala[maxn];
int ans[5*maxn];
struct A {
	int a,b;
} e[2*maxn];
struct node {
	bool f;
	int a,b;
} q[5*maxn];
map<pair<int,int>,int> vis;
void init() {
	for (int i=0; i<maxn; i++) pre[i] = i;
	vis.clear();
}

int find(int x) {
	if (x == pre[x]) return x;
	return  pre[x] = find(pre[x]);
}
void merge(int a,int b) {
	int ra = find(a);
	int rb = find(b);
	if (ra == rb) return ;
	if (rala[ra] > rala[rb]) pre[rb] = ra;
	else if (rala[ra] < rala[rb]) pre[ra] = rb;
	else if (rala[ra] == rala[rb]) {
		if (ra > rb) pre[ra] = rb;
		else pre[rb] = ra;
	}
	return ;
}
int n,Q,cnt;
int main() {
//	freopen("a.txt","r",stdin);
	bool mk=0;
	while (scanf("%d",&n) != EOF) {
		init();
		for (int i=0; i<n; i++) cin >> rala[i];
		int k;
		cin >> k;
		for (int i=0; i<k; i++) {
			int a,b;
			cin >> a >> b;
			if (a > b) swap(a,b);
			e[i].a = a;
			e[i].b = b;
			vis[{a,b}] = 1;
		}
		cin >> Q;
		for (int i=0; i<Q; i++) {
			string s;
			cin >> s;
			if (s == "query") {
				int x;
				cin >> x;
				q[i].a = x;
				q[i].f = 0;
			}
			else {
				int a,b;
				cin >> a >> b;
				if (a>b) swap(a,b);
				q[i].a = a;
				q[i].b = b;
				q[i].f = 1;
				vis[{a,b}] = 0;
			}
		}
		map<pair<int,int>,int>::iterator it;
		for (it=vis.begin(); it!=vis.end(); it++) 
			if (it->second) 
				merge(it->first.first,it->first.second);
		
		cnt = Q;
		for (int i=Q-1; i>=0; i--) {
			if (q[i].f == 0) { //查询
				cnt--;
				int cur = q[i].a;
				if (rala[find(cur)] > rala[cur] ) ans[cnt] = find(cur);
				else ans[cnt] = -1;
			}
			else merge(q[i].a,q[i].b);
		}
		if (mk) printf("\n");		
		else mk = 1;
		for (int i=cnt; i<Q; i++) 
			printf("%d\n",ans[i]);
	}
	return 0;
}
算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！