从Leetcode 每日一题练习继续讨论：
2097. 合法重新排列数对
2097. Valid Arrangement of Pairs
题解
本题是一道典型的图问题，每一个pair有一个start和end相当于一个有向边的起始和终止节点。而本题即找图中一条可以一次性经过图中全部边且不重复的路径问题，也就是一个欧拉图问题。这种图问题如果不了解相关知识是比较难解的，像在一个欧拉图中寻找欧拉路径的问题当前已经有比较经典的算法，故本题可以使用Hierholzer算法解决。注意本题中要寻找的是欧拉通路而不是欧拉回路。对于欧拉图的简单介绍可以参考
代码
class Solution {
public:
vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
unordered_map<int, vector<int>> graph;
unordered_map<int, int> inDegree, outDegree;
for (const auto& pair : pairs) {
int u = pair[0], v = pair[1];
graph[u].push_back(v);
outDegree[u]++;
inDegree[v]++;
}
int start = pairs[0][0];
for (const auto& [node, _] : graph) {
if (outDegree[node] > inDegree[node]) {
start = node;
break;
}
}
deque<int> path;
stack<int> stk;
stk.push(start);
while (!stk.empty()) {
int u = stk.top();
if (graph[u].empty()) {
path.push_front(u);
stk.pop();
} else {
stk.push(graph[u].back());
graph[u].pop_back();
}
}
vector<vector<int>> result;
for (auto it = path.begin(); it != prev(path.end()); ++it) {
result.push_back({*it, *next(it)});
}
return result;
}
};