[LeetCode]Sequence Reconstruction

根据题目描述就知道又是一个建图的问题。每一个数字就是一个vertex，每一个给定的先后关系就是一个edge。然后重建先后顺序就是一个topological sorting的过程。当然根据题目所说重建顺序唯一，我们每次发现多于一个可去掉的顶点时就需要return false，这样可以保证sorting结果唯一。另外有环的情况，有环的话我们能sort的vertex集合是所有vertex集合的子集，因为环的部分我们不可能sort，所以我们发现sort出来的集合大小和原图不一样的话，那就是说明有环，也需要return false。代码如下：

	class Solution {
	public:
	bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
	unordered_map<int, vector<int>> g;
	unordered_map<int, int> indegrees;
	for(auto& seq : seqs)
	{
	for(int i = 0; i < seq.size(); ++i)
	{
	if(!i && indegrees.find(seq[i]) == indegrees.end())
	indegrees[seq[i]] = 0;
	if(i < seq.size() - 1)
	{
	g[seq[i]].emplace_back(seq[i + 1]);
	++indegrees[seq[i + 1]];
	}
	}
	}
	queue<int> leaves;
	for(auto& p : indegrees)
	if(!p.second)
	leaves.push(p.first);
	//topological sorting
	vector<int> res;
	while(leaves.size())
	{
	if(leaves.size() != 1)
	return false;
	int node = leaves.front();
	res.emplace_back(node);
	leaves.pop();
	for(auto next : g[node])
	if(--indegrees[next] == 0)
	leaves.push(next);
	}
	return res == org && org.size() == indegrees.size();//in case there is circle e.g. [1] ,[[1],[2,3],[3,2]]
	}
	};

view raw Sequence Reconstruction.cpp hosted with ❤ by GitHub