拓扑序

269. Alien Dictionary

题意：给一个排好序的String Array，找出他们每个元素之间的顺序关系。

卡住的地方：如何插入新的node。如何去构造一个有向图。

复习一下构建有向图的方法：

假设我们有3条边：A->C, B->C, C->D，先将每个节点的计数器初始化为0。然后我们对边遍历时，每遇到一个边，把目的节点的计数器都加1。然后，我们再遍历一遍，找出所有计数器值还是0的节点，这些节点就是有向无环图的“根”。然后我们从根开始广度优先搜索。具体来说，搜索到某个节点时，将该节点加入结果中，然后所有被该节点指向的节点的计数器减1，在减1之后，如果某个被指向节点的计数器变成0了，那这个被指向的节点就是该节点下轮搜索的子节点。 在实现的角度来看，我们可以用一个队列，这样每次从队列头拿出来一个加入结果中，同时把被这个节点指向的节点中计数器值减到0的节点也都加入队列尾中。需要注意的是，如果图是有环的，则计数器会产生断层，即某个节点的计数器永远无法清零（有环意味着有的节点被多加了1，然而遍历的时候一次只减一个1，所以导致无法归零），这样该节点也无法加入到结果中。所以我们只要判断这个结果的节点数和实际图中节点数相等，就代表无环，不相等，则代表有环。

简而言之： 遍历边，初始化 计算入度 BFS

解法： 图的表示方法有两种。 邻接矩阵和邻接链表 用HashMap来表示方便维护：HashMap<Character, Set<Character>>

如何根据字典建图呢？其实边都暗藏在相邻两个词之间，比如abc和abd，我们比较两个词的每一位，直到第一个不一样的字母c和d，因为abd这个词在后面，所以d在字母表中应该是在c的后面。 所以每两个相邻的词都能蕴含一条边的信息。

因为字典里面可能有重复的边，所有要先判断，已经添加过的边不要重复添加。

BFS的时候就是不断去找indegree为零的点加入Queue中，然后再把该点邻接的点的入度减一，直到所有的点的入度都为零，否则就是有环存在。