HiHo一下第13~15周

發表於   |   分類於

正文

[HiHo一下]第13~15周主要通过例子来阐述LCA问题的朴素解法以及Tarjan离线算法，同时兼顾介绍Tarjan算法使用到的一个数据结构——并查集。

HiHo一下第13周

问题描述参见标题链接，不再重复叙述。使用朴素解法即可AC，下面图示说明一下朴素解法的过程并给出相应AC代码：

LCA朴素解法

上图中的继承关系再明显不过了，求两个子节点的最近公共祖先，比如H 和 I。

我们一眼就可以看出结果是A。事实上，注意从H到A的路径与从I到A的路径，LCA问题的朴素解法实际上是求解两条交叉链表的第一个交点。

下面是AC代码，请不要吐槽为什么这么长以及代码复用率低下…… (T- T)

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <string>
#include <stdlib.h>
#include <map>
using namespace std;

struct Node
{
	Node* p;
	string name;
};

map<string, Node*> people;

int main(int argc, char** argv)
{
	int dataNum = 0;
	int reqNum = 0;
	cin >> dataNum;
	while (dataNum > 0)
	{
		string father, child;
		cin >> father >> child;
		Node* fn = NULL;
		Node* cn = NULL;
		auto fit = people.find(father);
		auto cit = people.find(child);
		if (fit == people.end())
		{
			fn = new Node();
			fn->name = father;
			fn->p = NULL;
			people.insert(pair<string, Node*>(father, fn));
		}
		else
		{
			fn = fit->second;
		}

		if (cit == people.end())
		{
			cn = new Node();
			cn->name = child;
			cn->p = NULL;
			people.insert(pair<string, Node*>(child, cn));
		}
		else
		{
			cn = cit->second;
		}
		cn->p = fn;
		--dataNum;
	}

	cin >> reqNum;
	for (; reqNum > 0; --reqNum)
	{
		string _1, _2;
		cin >> _1 >> _2;
		if (_1 == _2)
		{
		    cout << _1 << endl;
		    continue;
		}
		unsigned int step1 = 0, step2 = 0;
		auto _1it = people.find(_1);
		auto _2it = people.find(_2);
		if (_1it == people.end() || _2it == people.end())
		{
			cout << "-1" << endl;
			continue;
		}
		Node* _1n = _1it->second;
		Node* _2n = _2it->second;
		Node* _1temp = _1n;
		Node* _2temp = _2n;
		while (_1temp->p) { _1temp = _1temp->p; ++step1; }
		while (_2temp->p) { _2temp = _2temp->p; ++step2; }
		if (_1temp != _2temp)
		{
			cout << "-1" << endl;
			continue;
		}
		_1temp = _1n;
		_2temp = _2n;
		bool find = false;
		if (step1 > step2)
		{
			int s = step1 - step2;
			while (s > 0)
			{
				_1temp = _1temp->p;
				--s;
			}
			while (_2temp)
			{
				if (_1temp == _2temp)
				{
					cout << _1temp->name << endl;
					find = true;
					break;
				}
				_2temp = _2temp->p;
				_1temp = _1temp->p;
			}
		}
		else
		{
			int s = step2 - step1;
			while (s > 0)
			{
				_2temp = _2temp->p;
				--s;
			}
			while (_1temp)
			{
				if (_1temp == _2temp)
				{
					cout << _1temp->name << endl;
					find = true;
					break;
				}
				_2temp = _2temp->p;
				_1temp = _1temp->p;
			}
		}
		if (false == find)
		{
			cout << "-1" << endl;
		}
	}
	return 0;
}

HiHo一下第14周

第14周主要是说明并查集这一数据结构的应用，题目详见标题链接。

在《算法导论》中有关于并查集的论述，参见【不相交数据结构】一章。这里只对其做基本的说明并给出题目的AC代码。

首要一点：森林与集合之间是一个等价的关系，借用《算法导论》中的一幅图来说明：

并查集与森林

上图包含了三棵树，对于每一棵树，我们可以将其视为一个集合——于是我们有{c, h, e, b}，{f, d, g}，{f, c, h, e, b, d, g}三个集合，并且很明显第三个集合是前两个集合的并集。每一棵树的树根可以视为是对应集合的代表元素。

合并两棵树的操作只需要将一棵树的根节点作为另一棵树的根节点的孩子插入即可。集合之间的并运算也可以这样实现。

于是在进行元素归属操作的判定问题中，我们可以对给定元素，查找到它所在的树的根节点即可。

然而树的合并带来了一个这样的问题：在极端情况下，树的深度将会被拉长为一个单链表的结构，前面归属判定的操作将会退化为对单链表的遍历操作。

事实上，考虑到纯粹的集合元素之间并没有父——子这样的关系，我们可以通过对查找（或者称为上溯）路径的压缩来加快归属判定的求解：

路径压缩

压缩过程实际上就是将判定链上的所有元素直接接到代表元素上的过程，这一过程可以通过递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
ElemReference compress(ElemReference elem)
{
	if (elem is set's represent element)
	{
		return elem;
	}
	else
	{
		elem.represent = compress(elem.represent);
		return elem.represent;
	}
}

了解了上面的并查集的基本内容之后，就可以对题目进行编码了，下面给出AC代码：

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
100
101
102
103
104
105
106
107
108
109
110
#include <map>
#include <string>
#include <iostream>
using namespace std;

struct Node
{
	Node* p;
	string name;
};

map<string, Node*> mhash;

void compress(Node* n)
{
	// 最后一个节点不用压缩
	if (n == n->p)
	{
		return;
	}

	compress(n->p);

	if (n->p && n->p->p)
	{
		n->p = n->p->p;
	}
}

Node* getRoot(Node* n)
{
	while (n != n->p)
	{
		n = n->p;
	}
	return n;
}

int main(int argc, char** argv)
{
	unsigned int lineNum = 0;
	cin >> lineNum;

	for (;lineNum > 0;--lineNum)
	{
		int op = -1;
		string n1, n2;
		cin >> op >> n1 >> n2;
		auto i1 = mhash.find(n1);
		auto i2 = mhash.find(n2);
		Node* p1 = NULL;
		Node* p2 = NULL;
		if (op == 0)
		{
			//known
			if (i1 == mhash.end())
			{
				p1 = new Node();
				p1->p = p1;
				p1->name = n1;
				mhash.insert(pair<string, Node*>(n1, p1));
			}
			else
			{
				p1 = i1->second;
			}

			if (i2 == mhash.end())
			{
				p2 = new Node();
				p2->p = p2;
				p2->name = n2;
				mhash.insert(pair<string, Node*>(n2, p2));
			}
			else
			{
				p2 = i2->second;
			}

			getRoot(p1)->p = getRoot(p2);

			compress(p1);
			compress(p2);

		}
		else if (op == 1)
		{
			//unknown
			if (i1 == mhash.end() || i2 == mhash.end())
			{
				cout << "no" << endl;
				continue;
			}
			p1 = i1->second;
			p2 = i2->second;


			if (getRoot(p1) == getRoot(p2))
			{
				cout << "yes" << endl;
			}
			else
			{
				cout << "no" << endl;
			}
		}
	}

	return 0;
}

注意压缩操作的位置：可以在构建集合的过程中进行，也可以在查询的时候进行压缩，当然也可以不进行压缩——下面是三种策略对于同样的测试数据耗费的时间：

Comparative

事实上，上述代码依旧可以有优化的空间：压缩过程需要走一个查找链，同样查找链越长，递归压缩也就越耗费时间。这就要求在合并的时候尽量将比较“矮”的树合并到比较“高”的树上——即启发性合并。

HiHo一下第15周

第15周的问题主要是利用Tarjan算法来解决LCA问题，Tarjan算法用到了在14周中的并查集这一数据结构，同时该算法对递归的不同阶段进行了充分的利用，十分具有学习价值——在以后对动态语言使用的Garbage Collector的介绍中（三色标记法）将再次看到这一手段。下面对Tarjan算法进行分析，并给出相应的AC代码。

我们知道递归分为三个阶段：进入->处理->返回，Tarjan算法就是根据这三个阶段进行的：根据当前DFS的状态，给树中的节点赋予不同的颜色：未访问过的为白色，尚未递归返回的为红色，访问过的为绿色。以下图为例，我们来看看对于查询[D, E], [D, B], [I, J], [J, H]的求解过程。

Tarjan

初始情况下，所有的节点都是白色，我们DFS递归查找到节点D：

Find 'D'

此时与ID相关的查询[D, E], [D, B]中，B节点为红色，E节点为白色。通过观察，查询[D, B]的结果应该是B（__红色__）。由于查询无关元素的顺序，因此我们将查询[D, E]更改为查询[E, D]，并将其延后。

DFS继续进行，到达节点E：

Find 'E'

查询[E, D]的结果为B（红色），注意此时D（__绿色__）。

DFS继续进行，到达节点I：

Find 'I'

此时与I相关的查询[I, J]中，J为白色，将其转为查询[J, I]并延后。

DFS进行到节点J：

Find 'J'

相关查询[J, I], [J, H]中，I为绿色，H为白色。与以前一样，查询[J, H]，转为[H ,J]并延后。而对于查询[J, I]我们知道结果是A，而A则是由I向上遇到的__第一个红色节点__（可以给A添加一个父节点来验证一下）。

最后DFS进行到H：

Find 'H'

相关查询[H, J]中，J是绿色，顺着J向上找第一个红色节点，为C，正是我们想要的结果。

至此，Tarjan算法的主要过程已经完成了，按照这个过程已经可以编写能够正确工作的代码了。但是我们应当注意到整个过程依旧有需要改进的地方：如何比较高效地找到 第一个红色节点 。至此，可以引出我们前面讨论过的并查集了。

注意前面几张图中的绿色子树与他的父跟节点，前面提到过集合可以通过树来呈现出来，我们现在将绿色的子树（单独一个节点也算）视为一个集合，将他的红色的父根节点视为该集合的代表元素（注意这里的代表元素是集合外的一个元素了），于是我们就可以通过一个O(1)的查询来得到我们想要的那个红色节点了。

前面提到过，想要得到一个O(1)的查询，需要一个递归的压缩过程。回头再看压缩操作，它实际上也是一个DFS的操作，而这恰好与我们遍历树的方式一致，因此可以在遍历的过程中完成这个操作。

下面是我的代码，没有使用数组去解这个问题，在OJ上超时了…

另附一个AC的代码链接：点击这里

再附加另外一个讲解该算法的文：点击这里

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
using namespace std;

#define RED 2
#define GREEN 1
#define WHITE 0

struct Node
{
	string name;			// 名字
	int color;				// 颜色
	vector<Node*> children;	// 孩子们
	Node* parent;			// 父节点
	Node* represent;		// 所处集合的代表节点
	Node(string& s)
	{
		name = s;
		color = WHITE;
		parent = NULL;
		represent = this;
	}
};

struct Query
{
	Node* n1;
	Node* n2;
	string result;	// 查询结果
	Query()
	{
		n1 = NULL;
		n2 = NULL;
	}

	Query(Node* n_1, Node* n_2)
	{
		n1 = n_1;
		n2 = n_2;
	}

	void swapOrd()	// 当n2是白色的时候交换n1和n2位置
	{
		Node* t = n1;
		n1 = n2;
		n2 = t;
	}
};

map<string, Node*> myhash;	// for find
Node* root= NULL;
vector<Query*> querys;	// 原始查询列表
list<Query*> queReq;	// 查询队列

Node* compress(Node* n)
{
    if (n->color == RED)
    {
        return n;
    }
    n->represent = compress(n->represent);
    return n-> represent;
}

void printResult()
{
	for (unsigned int i = 0; i < querys.size(); ++ i)
	{
		cout << querys[i]->result << endl;
	}
}

void dfs(Node* n)
{
	if (n == 0)
	{
		return;
	}
	// 标记为红色
	n->color = RED;

	// 处理请求
	auto it = queReq.begin();
	for (; it != queReq.end();)
	{
		auto temp = it;
		it++;

		Query* q = * temp;
		if (q->n1 == q->n2)
		{
			q->result = q->n1->name;
			queReq.erase(temp);
			continue;
		}
		if (q->n1 == n)
		{
			if (q->n2->color == WHITE)
			{
				// 对于白色的n2，交换n1与n2
				q->swapOrd();
			}
			else if (q->n2->color == RED)
			{
				// 对于红色的n2，直接得到结果
				q->result = q->n2->name;
				// 移除当前队列元素
				queReq.erase(temp);
			}
			else
			{
				// 对于绿色的n2，其结果是它的represent
				compress(q->n2);
				q->result = q->n2->represent->name;
				// 移除当前队列元素
				queReq.erase(temp);
			}
		}
	}

	// dfs
	for (unsigned int i = 0; i < n->children.size(); ++i)
	{
		Node* child = n->children[i];

		dfs(child);
	}

	n->color = GREEN;
};

int main(int args, char** argv)
{
	int data = 0, req = 0;
	cin >> data;
	string s1, s2;
	// 建树
	Node* father = NULL;
	Node* son = NULL;
	while (data > 0)
	{
		cin >> s1 >> s2;
		auto it1 = myhash.find(s1);
		auto it2 = myhash.find(s2);

		if (it1 == myhash.end())
		{
			father = new Node(s1);
			myhash.insert(pair<string, Node*>(s1, father));
		}
		else
		{
			father = it1->second;
		}

		if (it2 == myhash.end())
		{
			son = new Node(s2);
			myhash.insert(pair<string, Node*>(s2, son));
		}
		else
		{
			son = it2->second;
		}

		son->parent = father;
		son->represent = father;
		// a son has only one father. Not check here.
		father->children.push_back(son);
		data--;
	}
	// 确定所有人的根（根据题目说明，所有人都有一个公共祖先）
	while (son->parent)
		son = son->parent;
	root = son;
	// Query collection
	cin >> req;
	while (req > 0)
	{
		cin >> s1 >> s2;

		auto it1 = myhash.find(s1);
		auto it2 = myhash.find(s2);

		Node* n1 = it1->second;
		Node* n2 = it2->second;

		Query* p = new Query(n1, n2);

		querys.push_back(p);
		queReq.push_back(p);

		req--;
	}
	dfs(root);
	printResult();
	return 0;
}