[拓扑排序][dfs]leetcode5665：从相邻元素对还原数组(medium)

拓扑排序][dfs]leetcode5665：从相邻元素对还原数组(medium)"/>

[拓扑排序][dfs]leetcode5665：从相邻元素对还原数组(medium)

题目：

题解：

本题最难的是将这个实际问题转换为图论问题来做，我比赛就没想到，然后等比赛结束了，看到别人的思路才知道这题原来这么简单。

---

思路1：拓扑排序

• 构建无向图，然后记录顶点的度（注意是总度数=入度+出度），由于起点和终点只出现了一次，所以度为1，而其他点出现的两次（度为2），而此时按题目的意思，我们每次都要选度为1的点作为起点就进行遍历，这样就转换为topsort问题了。

思路二：DFS

• 遍历无向树，这棵树是比较特别是一棵单边的无向树，所以直接dfs遍历即可，主要防止无向树向根节点回搜，需要判断邻节点与父节点相等与否x!=father。

代码如下：

class Solution {
public:// 利用topsort来做，由于起点和终点只出现一次，即起点出度为1，终点入度为1// 而其他中间的点出现了2次，即入度和出度都为1，总度数为2// 现在我们利用topsort的思想将度为1的加入队列，进行bfs就行vector<int> restoreArray_1(vector<vector<int>>& adjacentPairs) {unordered_map<int,vector<int>> graph;// 构建邻接表unordered_map<int,int> indegree;// 记录顶点的度// 构建邻接边和记录顶点的度for(auto edge:adjacentPairs){int a=edge[0],b=edge[1];graph[a].push_back(b),graph[b].push_back(a);indegree[a]++,indegree[b]++;}// 寻找起点和终点，即度为1的点int start=INT_MAX,end=INT_MAX;for(auto [k,v]:indegree){if(v==1&&start==INT_MAX)start=k;else if(v==1&&end==INT_MAX)end=k;else if(start!=INT_MAX&&end!=INT_MAX)break;}// 进行topsortqueue<int> q;q.push(start);vector<int> res(adjacentPairs.size()+1,0);int cnt=0;while(!q.empty()){int t=q.front();q.pop();res[cnt++]=t;// 遍历t的所有邻接边，将邻接边的度都减1for(auto g:graph[t]){indegree[g]--;// 将总度数为1的点加入队列，为下次的起点if(indegree[g]==1)q.push(g);}}// 因为最后终点还没加入res中，所以要加入进去res.back()=end;return res;}unordered_map<int,vector<int>> graph;vector<int> res;void dfs(int u,int father){// 将当前节点加入路径res.push_back(u);for(auto x:graph[u])if(x!=father)// 防止无向树搜回去dfs(x,u); }vector<int> restoreArray(vector<vector<int>>& adjacentPairs){unordered_map<int,int> indegree;// 记录顶点的度// 构建邻接边和记录顶点的度for(auto edge:adjacentPairs){int a=edge[0],b=edge[1];graph[a].push_back(b),graph[b].push_back(a);indegree[a]++,indegree[b]++;}// 寻找起点，即度为1的点int start=0;for(auto [k,v]:indegree){if(v==1){start=k;break;}}// 进行dfsdfs(start,100001);return res;}
};