Leetcode 2097 - Legal rearrangement of pairs

One 、 Title Description

Two 、 analysis

It's not hard to find out , This problem is actually taking different numbers as vertices in the graph , Will all pair End to end , Then find a path that accesses all edges exactly once .

3、 ... and 、 Algorithm

1、 Euler pathway

The above analysis is the same as the definition of Euler path . Relevant definitions and algorithms of Euler graph can be referred to 『 graph theory 』 Getting started and Hierholzer Algorithm .
The description of the algorithm is as follows ：

（1） Realization

The following algorithm records the incoming and outgoing nodes of all points to compare ：

struct Vertex {
    
    unordered_set<int> ins;
    unordered_set<int> outs;
};

vector<int> hierholzer(unordered_map<int, Vertex>& vertexes) {
    
	//  Determine the starting point of Euler circuit 
	int startIndex = vertexes.begin()->first;
	int n = vertexes.size();
	for (auto& vertex : vertexes) {
    
		if (vertex.second.outs.size() - vertex.second.ins.size() == 1) {
    
			startIndex = vertex.first;
		}
	}
	
	//  Use  dfs  Determine the access reverse order of the loop 
	stack<int> s;
	function<void(int)> dfs = [&](int index) {
    
		while (1) {
    
			if (vertexes[index].outs.empty()) {
    
				break;
			}
			
			//  Delete an adjacent edge 
			auto iter = vertexes[index].outs.begin();
			int next = *iter;
			vertexes[index].outs.erase(iter);
			vertexes[next].ins.erase(index);
			dfs(next);
		}
		
		//  No adjacent edges , Stack vertices 
		if (vertexes[index].outs.empty()) {
    
			s.push(index);
		}
	};
	dfs(startIndex);
	
	//  Reverse order return 
	vector<int> ret;
	while (!s.empty()) {
    
		ret.push_back(s.top());
		s.pop();
	}

	return ret;
}

（2） Optimize

actually , In addition to determining the starting point, we need to compare the out degree and in degree , In other cases, we only need the output of nodes . therefore , We can only keep the number of degrees , There is no need to maintain the number of degrees at all times in the process . When you only need to update the out degree node , We can use vector To optimize the deletion speed . The optimized implementation is as follows ：

vector<int> hierholzer(unordered_map<int, vector<int>>& edges, unordered_map<int, int>& inDegrees, unordered_map<int, int>& outDegrees) {
    
	int startIndex = inDegrees.begin()->first;
	for (auto& out : outDegrees) {
    
		int index = out.first;
		if (out.second > inDegrees[index]) {
    
			startIndex = index;
			break;
		}
	}

	stack<int> s;
	function<void(int)> dfs = [&](int index) {
    
		while (!edges[index].empty()) {
    
			auto next = edges[index].back();
			edges[index].pop_back();
			dfs(next);
		}

		s.push(index);
	};
	dfs(startIndex);

	vector<int> ret;
	while (!s.empty()) {
    
		ret.push_back(s.top());
		s.pop();
	}

	return ret;
}

2、 Realization

class Solution {
    
public:
	vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
    
		unordered_map<int, int> inDegrees, outDegrees;
		unordered_map<int, vector<int>> edges;
		for (auto& p : pairs) {
    
			++outDegrees[p[0]];
			++inDegrees[p[1]];
			edges[p[0]].push_back(p[1]);
		}

		auto circle = hierholzer(edges, inDegrees, outDegrees);
		int c = circle.size();
		vector<vector<int>> ret(c - 1, vector<int>(2));
		for (int i = 0; i < circle.size() - 1; ++i) {
    
			ret[i][0] = circle[i];
			ret[i][1] = circle[i + 1];
		}

		return ret;
	}
};