题目介绍
题目难度: easy
给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。
题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/destination-city
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目样例
示例 1：输入：paths = [[“London”,“New York”],[“New York”,“Lima”],[“Lima”,“Sao Paulo”]]
输出：“Sao Paulo”
解释：从 “London” 出发，最后抵达终点站 “Sao Paulo” 。本次旅行的路线是 “London” -> “New York” -> “Lima” -> “Sao Paulo” 。
示例 2：
输入：paths = [[“B”,“C”],[“D”,“B”],[“C”,“A”]]
输出：“A”
解释：所有可能的线路是：
“D” -> “B” -> “C” -> “A”.
“B” -> “C” -> “A”.
“C” -> “A”.
“A”.
显然，旅行终点站是 “A” 。
示例 3：
输入：paths = [[“A”,“Z”]]
输出：“Z”
本题就是典型的拓扑排序题
拓扑排序是将有向无环图
(
V
，
E
)
(V，E)
(V，E)排列成一个有序排列
显然对于边
(
i
,
j
)
∈
E
(i,j) \in E
(i,j)∈E 则在有序排列中，顶点i必然位于顶点j之前。
因此拓扑排序的方法就是每次找到一个没有入度的点，并将所有的出边删除。重复n次后则得到有序排列。
算法思路 1
当然本题并不要求拓扑排序，而只是要终点，所以像力扣君的题解，找到入边集中不存在鱼出边集的点即可。
算法实现
1.官方题解的思路是记录所有的出边
然后对所有的入边进行查询
set.cout复杂度是（logn+an）
所以实际复杂度接近于（nlogn）
class Solution {
private:
unordered_set<string> citiesA;
public:
string destCity(vector<vector<string>> &paths) {
for (auto &path : paths) {
citiesA.insert(path[0]);
}
for (auto &path : paths) {
if (!citiesA.count(path[1])) {
return path[1];
}
}
return "";
}
};
2.这里我的实现略有不同
相同在于都保存了出点集
不同在于对于入点集使用了map也进行了保存
因此遍历出点集将入点集对应元素进行删除（erase是O(logn)复杂度高 而使用map 增加了value值只要O(1)）
然后遍历入点集找到value为true做返回
map的下标访问复杂度为O(logn)
实际复杂度还是O(nlogn)
class Solution {
public:
string destCity(vector<vector<string>> &paths) {
unordered_set<string> citiesA;
//出边集
unordered_map<string,bool> citiesB;
//入边集
for (auto &path : paths) {
citiesA.insert(path[0]);
citiesB[path[1]] = 1;
}
for(auto &path:citiesA){
citiesB[path] = false;
}
for(auto&path:citiesB){
if(path.second)
return path.first;
}
return "";
}
};
并查集
对于拓扑排序问题并查集是一种很好的数据结构。
并查集结构其实是一种多链表结构，就像森林一样，分为不同的集合。或者不同的树。
然后通过一定的方式组合起来。
不同的是，对于并查集我们关心的是属于哪个集合，所以体现的是节点与根的关系。
（根则表明了是哪个集合），因此实际并查集与树是完全相反的两种结构，一种向下。一种向上。
那么因此我们的并查集其实指针域只有一个指针，就是父指针。
当我们进行判定两个节点是否属于一个时，我们就可以通过findroot()函数找到两个节点的根是否相同。
同时由于这种前序关系，我们发现很适合来解决拓扑排序的问题。（因为图不是树，是很难确定根在哪里的，而这里每个节点都必然有一个自己的根）
并查集支持两种操作，findroot()和union();
并查集ADT
struct listnode{
type data;
listnode *pre;
}
class unionfind{
private:
Listnode elem[max];
public:
Listnode find();
void union(listnode p,listnode q);
}
- find()
find(Listnode p){ while(p!=p->pre) p = p->pre; return p; } - union
union(listnode p,listnode q){ p = find(p); q = find(q); p->pre = q; //q->pre = p也可 //if p = q, p ->pre = p = q } - del
由于本题是想要将所有前序节点删除找到终点因此构造了一个新的del函数，del函数会将node的所有前序节点删除。del(listnode node){ if(node!=node->pre){ listnode parent = node->pre; do{ const listnode i = parent; //保存当前节点地址 parent = parent->pre; //更新parent; i->pre = i; //从集合中删除i del i; //删除节点i }while(parent!=parent->pre); del parent; //parent指向原集合的根因此也需要删除 }// 如果是根节点则没有前序则不进行操作 node->pre = node; //前序删除变成集合根节点 }
算法实现
为了实现节点的删除此处使用bool记录是否存在
查询复杂度是logn的
实际删除次数为n次
时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
#define x first
#define y second
class Solution {
private:
unordered_map<string ,pair<string ,bool>> fset;
void init(vector<vector<string>>& paths) {
int &&size = paths.size();
for(int i = 0;i<size;i++){
string &in = paths[i][1];//入点
string &out = paths[i][0];//出点
pair<string,bool> &&node = make_pair(paths[i][0],true);
fset[in] = node;
//入点的前置是出点
fset[out] = fset[out].x.length()?fset[out]:node;
//出点如果没有保存过则进行保存
}
}
void del(string s){
string parent = fset[s].x;
if(s!=parent){//s!=s.next
do{
const string i = parent;
parent = fset[parent].x;
fset[i].y = false;
//删除parent的后置节点
fset[i].x = i;
//将节点从集合中删除
}while(parent!=fset[parent].x);
fset[parent].y = false;
//删除s所属集合的根
}
fset[s].x = s;
}
public:
string destCity(vector<vector<string>>& paths) {
// fset.clear();
//slist.clear();
init(paths);
for(auto i = fset.begin();i!=fset.end();i++){
del(i->first);
}
for(auto i:fset){
auto &node = i.y;
if(node.y)
return node.x;
}
return "";
}
};
};
队列实现拓扑排序
本题队列实现比较困难的一点在于入度和边表的存储。
由于map对于离散化数据存储的优点
因此使用两个map分别存储入度和边表并且做初始化即可
每次查询入度表内入度为零且存在的节点入队，并做删点和删边操作
删除所有节点后s记录的一定是终点
算法实现
#define indeg first
#define exist second
class Solution {
private:
queue<string> q;
unordered_map<string ,pair<int,bool>> inlist;
unordered_map<string,vector<string>> edge;
void init(vector<vector<string>>& paths) {
pair<int,bool> &&empty = make_pair(0,true);
for(auto node:paths){
const string &in = node[1];
const string &out = node[0];
edge[out].push_back(in);
//out顶点push出边
inlist[out] = inlist[out].indeg?inlist[out]:empty;
//初始化out点的入度
inlist[in] = inlist[in].indeg?inlist[in]:empty;
//初始化in点的入度
inlist[in].indeg++;
//入度更新
}
}
public:
string destCity(vector<vector<string>>& paths) {
// fset.clear();
//slist.clear();
string s;
init(paths);
int size = inlist.size();
while(size){
for(auto i:inlist){
const auto node = i.second;
if(!node.indeg&&node.exist){
//如果入度为零且存在则入队进行删边和删点
q.push(i.first);
}
}
while(!q.empty()){
string node = q.front();
s = node;
//总是更新为当前无前置的节点
q.pop();
inlist[node].exist = 0;
//删除节点
size--;
//节点少一
if(edge[node].size())
for(auto i:edge[node]){
const string next = i;
inlist[next].indeg--;
//删掉node的所有出边
}
}
}
return s;
}
};