发现网上很多代码（包括一些号称100分的代码）都存在一些技术问题，致使提交之后出现RE并且只有80分，因此写了这篇笔记。
针对这些代码的问题进行了简单的分类：
1. .bss段溢出。静态分配了规模达到MxN=1e9 B≈1e3 MB的二维数用来存储邻接矩阵（题目所给出的是稠密图）。但最坑的问题是在DevC++/MinGW环境下，即使.bss段溢出仍然可以通过编译，没有任何错误或警告，程序也能在输入数据规模较小的情况下正常运行，这使得问题比较隐蔽。
2. 递归调用过深，导致爆栈（栈空间溢出）。因为程序调用栈的动态性，这个问题同样非常隐蔽，关键是难以预估系统为我们分配了多大的栈空间。经过实测，在DevC++/MinGW环境下，系统为程序分配的堆栈空间大约只有128KiB，本题中dfs函数递归调用32496帧（1e4）后程序就崩溃了，递归的深度是在程序抛出异常后通过gdb观察到的。
综上解决办法如下：
针对问题1，改用邻接表或链式前向星存储图即可；
针对问题2，有两种解决方案：一是改进算法，修改为显式用栈的DFS；二是手动扩栈，相比于传统的#pragma，本文将介绍一种通用性很强的内联汇编扩栈方法，关于该方法的原理在日后会详细介绍（如果有必要的话）。
先把原题贴在这里，方便查阅：
| 试题编号： | 201512-4 |
| 试题名称： | 送货 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： |
问题描述
为了增加公司收入，F公司新开设了物流业务。由于F公司在业界的良好口碑，物流业务一开通即受到了消费者的欢迎，物流业务马上遍及了城市的每条街道。然而，F公司现在只安排了小明一个人负责所有街道的服务。 任务虽然繁重，但是小明有足够的信心，他拿到了城市的地图，准备研究最好的方案。城市中有n个交叉路口，m条街道连接在这些交叉路口之间，每条街道的首尾都正好连接着一个交叉路口。除开街道的首尾端点，街道不会在其他位置与其他街道相交。每个交叉路口都至少连接着一条街道，有的交叉路口可能只连接着一条或两条街道。 小明希望设计一个方案，从编号为1的交叉路口出发，每次必须沿街道去往街道另一端的路口，再从新的路口出发去往下一个路口，直到所有的街道都经过了正好一次。 输入格式 输入的第一行包含两个整数n, m，表示交叉路口的数量和街道的数量，交叉路口从1到n标号。 接下来m行，每行两个整数a, b，表示和标号为a的交叉路口和标号为b的交叉路口之间有一条街道，街道是双向的，小明可以从任意一端走向另一端。两个路口之间最多有一条街道。 输出格式 如果小明可以经过每条街道正好一次，则输出一行包含m+1个整数p1, p2, p3, ..., pm+1，表示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证p1最小，p1最小的前提下再保证p2最小，依此类推。 如果不存在方案使得小明经过每条街道正好一次，则输出一个整数-1。 样例输入 4 5 1 2 1 3 1 4 2 4 3 4 样例输出 1 2 4 1 3 4 样例说明 城市的地图和小明的路径如下图所示。 1 2 1 3 1 4 2 4 3 4 2 3 样例输出 -1 样例说明 城市的地图如下图所示，不存在满足条件的路径。 前50%的评测用例满足：1 ≤ n ≤ 100, n-1 ≤ m ≤ 10000。 所有评测用例满足：1 ≤ n ≤ 10000，n-1 ≤ m ≤ 100000。 |
本文仅在之前代码的基础上，手动调用malloc分配了一块虚存，然后通过内联汇编直接修改ESP/RSP栈指针寄存器，将栈空间指向新分配的虚拟内存，从而改变当前栈空间。当然事情还没有这么简单，当main函数返回时，程序实际上会回溯最原始的运行时库中去，原始的栈空间中仍有数据，但此时我们新指定的栈已经空了，如果不还原栈指针寄存器的地址为运行时库分配的地址，会导致栈失去平衡，从而使程序崩溃，因此我们事先将原始栈指针保存到一个变量中，在main函数return之前恢复栈指针的值即可实现无缝衔接。
具体实现位于源程序Line 73~82和Line 149~153。这里需要利用预处理宏__i386__区分当前处理器体系是x86还是x86_64，因为32bit体系使用ESP存储栈指针，而64bit体系使用RSP。除非预先知道OJ使用的系统字长，否则应当保守处理，将针对两种体系的版本都写好。
1 /*
2 * 欧拉路径问题
3 *
4 * 无向图存在欧拉路径的充要条件是：
5 * 1. 图各个顶点连通（是连通图）
6 * 2. 各顶点的度都为偶数，或者至多存在两个顶点度为奇数（则这两个顶点为起点或终点）
7 *
8 * 因此先利用并查集判断图中各个顶点是否都连通，然后判断有无度为奇数的顶点，如果有，则这些点要么是起点要么是终点。
9 * 当符合欧拉路径的条件时，依题意直接从顶点1开始进行DFS（穷举的对象是边，不是顶点）
10 * 即可找出欧拉路径。假如题目换一下，不能确定起点为1，应该考虑fleury算法。
11 *
12 * 本题给出的图为稠密图（M<=1e5），直接DFS出现栈溢出错误。简单的解决方案是手工分配更大的栈空间（malloc），
13 * 然后通过修改ESP或RSP寄存器使得当前栈指向新分配的空间。这里需要注意当main函数返回之前，应当恢复之前的
14 * 栈指针寄存器，否则会造成返回到crt时栈不平衡。
15 */
16 #include <iostream>
17 #include <vector>
18 #include <stack>
19 #include <queue>
20 #include <algorithm>
21
22 #include <fstream>
23
24 #define N 10000+2
25 #define M 100000+2
26
27 using namespace std;
28
29 struct edge {
30 int u, m;
31
32 inline bool operator<(const edge &e) const {
33 return u < e.u;
34 }
35 };
36
37 static vector<edge> con[N];
38 static int deg[N];
39 static int parent[N];
40
41 static char vism[M];
42 static stack<int> path;
43
44 static int uf_find(int a) {
45 if (parent[a] == a)
46 return a;
47 else
48 return (parent[a] = uf_find(parent[a]));
49 }
50
51 static inline void uf_union(int a, int b) {
52 int pa = uf_find(a);
53 int pb = uf_find(b);
54 if (pa != pb) {
55 parent[pa] = pb;
56 }
57 }
58
59 static void search(int cur) {
60
61 for(size_t i=0; i<con[cur].size(); ++i) {
62 const edge &e = con[cur][i];
63 if (!vism[e.m]) {
64 vism[e.m] = 1;
65 search(e.u);
66 }
67 }
68
69 path.push(cur);
70 }
71
72 int main(void) {
73 register char *sp;
74 int size = 10 << 20; // 10MB
75 char *p = (char*)malloc(size) + size;
76 #ifdef __i386__
77 __asm__("movl %%esp, %0\n" :: "r"(sp));
78 __asm__("movl %0, %%esp\n" :: "r"(p));
79 #else
80 __asm__("mov %%rsp, %0\n" :: "r"(sp));
81 __asm__("mov %0, %%rsp\n" :: "r"(p));
82 #endif
83 ios::sync_with_stdio(false);
84
85 fstream fin("input1.txt");
86 cin.rdbuf(fin.rdbuf());
87
88 int n,m;
89 cin >> n >> m;
90
91 for(int i=1; i<=n; ++i) {
92 parent[i] = i;
93 }
94 for(int i=0; i<m; ++i) {
95 int a,b;
96 edge e;
97 cin >> a >> b;
98 e.m = i;
99 e.u = b;
100 con[a].push_back(e);
101 e.u = a;
102 con[b].push_back(e);
103 ++deg[a]; ++deg[b];
104 uf_union(a,b);
105 }
106
107 bool conn = true;
108 int p1 = uf_find(1);
109 for(int i=2;i<=n; ++i) {
110 int pi = uf_find(i);
111 if (pi != p1) {
112 conn = false;
113 break;
114 }
115 }
116
117 if (!conn) {
118 cout << -1 << endl;
119 } else {
120 vector<int> start;
121 int odd = 0;
122 for(int i=1; i<=n; ++i) {
123 sort(con[i].begin(), con[i].end());
124 if (deg[i] & 1) {
125 ++odd;
126 start.push_back(i);
127 }
128 }
129
130 if (odd <= 2 && find(start.begin(), start.end(), 1)!=start.end()) {
131 search(1);
132
133 while(!path.empty()) {
134 int t = path.top();
135 path.pop();
136 cout << t;
137 if (path.empty()) {
138 cout << endl;
139 } else {
140 cout << " ";
141 }
142 }
143
144 } else {
145 cout << -1 << endl;
146 }
147 }
148
149 #ifdef __i386__
150 __asm__("movl %0, %%esp\n" :: "r"(sp));
151 #else
152 __asm__("mov %0, %%rsp\n" :: "r"(sp));
153 #endif
154 return 0;
155 }