今天考试的题，顺便写一个题解。
思路
这道题让我们还原一个 DFS 序，
思路很简单：我们从第一个点开始，如果当前的点到的下一个点没有边了话，就建一条边。然后跳转到下一个点。
思路清楚了，只要注意代码实现就可以了。
AC 代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int T, n, m;
vector<int> e[N];
int maxn[N];
bool edge(int u, int v) { // 判断 u,v 之间有没有边。auto it = lower_bound(e[u].begin(), e[u].end(), v);return it != e[u].end() && *it == v;
}
void input() {cin >> n >> m;for (int i = 1; i <= n; i++) {e[i].clear();}for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}
}
void init() {for (int i = 1; i <= n; ++i) {if (!e[i].empty()) {sort(e[i].begin(), e[i].end());maxn[i] = e[i].back();} else {maxn[i] = 0;}}
}
int solve() {int ans = 0;stack<int> s;s.push(1);for (int v = 2; v <= n; v++) {while (true) {int u = s.top();if (edge(u, v)) {s.push(v);break;}if (maxn[u] < v && s.size() > 1) {s.pop();}else {ans++;s.push(v);break;}}}return ans;
}
signed main() {cin >> T;while (T--) {input();init();cout << solve() << endl;}return 0;
}