预备知识
有向无环图（DAG图）
顶点活动图（AOV图）：类似于流程图，顶点表示活动，箭头表示先后顺序
找到做事情的先后顺序，拓扑排序的结果可能不是唯一的
1.找出图中入度为0的点，然后输出
2.删除与改点相连接的边
3.重复1、2操作，直到图中没有点
拓扑排序方法论
借助队列进行BFS
1.初始化：把所有入度为0的点加入到队列
2.删除与改点连接的边。
3.当队列不为空时：a.拿出队头元素，加入到最终结果中b.删除与该元素相连的边
c.判断与删除边相连的点是否入度为0，如果入度为0，加入到队列中
实战
leetcode210.课程表2
现在总共有 numCourses 门课需要选，记为 0 到 numCourses-1。
给定一个数组 prerequisites ，它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。 例如 prerequisites[i] = [ai, bi] 表示想要学习课程 ai ，需要先完成课程 bi 。
请根据给出的总课程数 numCourses 和表示先修顺序的 prerequisites 得出一个可行的修课序列。
可能会有多个正确的顺序，只要任意返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: numCourses = 2, prerequisites = [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3:
输入: numCourses = 1, prerequisites = []
输出: [0]
解释: 总共 1 门课，直接修第一门课就可。
提示:
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
思路
思路：首先建图：unordered_map<int,vector>，或vector<vector>,前者表示所表示的顶点，后者表示该点所指向的点的集合。
然后找度为0的点加入到队列中
最后进入BFS，每次从队头取出元素插入到ans数组中，同时遍历改点所连接的边，把它指向的点的度–。如果等于0，则加入队列，最后得出答案，如果ans数组的size最后等于n，则返回ans，否则返回空
代码
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int,vector<int>> edges(numCourses);
vector<int> in(numCourses);//表示每个点的入度
vector<int> ans;
//构建图
for(auto p:prerequisites)
{
int a=p[0],b=p[1];//b->a
edges[b].push_back(a);
in[a]++;
}
//找入度为0的点
queue<int> q;
for(int i=0;i<numCourses;i++)
{
if(in[i]==0)
{
q.push(i);
}
}
//BFS
while(q.size())
{
int tmp=q.front();q.pop();
ans.push_back(tmp);
for(auto v:edges[tmp])
{
in[v]--;
if(in[v]==0)
q.push(v);
}
}
if(ans.size()==numCourses)
return ans;
return {};
}
};
leetcode 114.火星字典
现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 “” 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
字符串 s 字典顺序小于 字符串 t 有两种情况：
在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
示例 1：
输入：words = [“wrt”,“wrf”,“er”,“ett”,“rftt”]
输出：“wertf”
示例 2：
输入：words = [“z”,“x”]
输出：“zx”
示例 3：
输入：words = [“z”,“x”,“z”]
输出：“”
解释：不存在合法字母顺序，因此返回 “” 。
提示：
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 仅由小写英文字母组成
代码
class Solution {
unordered_map<char,unordered_set<char>> edges;//邻接表来存图
unordered_map<char,int> in;//统计入度
bool check=false;//处理边界情况
public:
string alienOrder(vector<string>& words) {
//1.建图+初始化入度哈希表
for(auto& s:words)
{
for(auto ch:s)
{
in[ch]=0;
}
}
int n=words.size();
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
add(words[i],words[j]);
if(check)return "";
}
}
queue<char> q;
for(auto& [a,b]:in)
{
if(b==0)q.push(a);
}
string ret;
while(q.size())
{
char t=q.front();q.pop();
ret+=t;
for(char ch:edges[t])
{
if(--in[ch]==0)
q.push(ch);
}
}
for(auto& [a,b]:in)
if(b!=0)
return "";
return ret;
}
void add(string s1,string s2)
{
int n=min(s1.size(),s2.size());
int i=0;
for(;i<n;i++)
{
if(s1[i]!=s2[i])
{
char a=s1[i];
char b=s2[i];
//a->b,构建图
if(!edges.count(a)||!edges[a].count(b))//a没有存过，a存过，看有没有a-》b的信息
{
edges[a].insert(b);
in[b]++;
}
break;
}
}
if(i==s2.size()&&i<s1.size())
check=true;
}
};
