boolean[] mark;//之前已经遍历的节点
boolean[] on;//本此路径上的节点
boolean flag;//是否有环
String ans;//结果,模拟栈
Deque[] adj;//邻接表
//添加v到w的边
public void addEdge(int v,int w){
if(adj[v]==null) adj[v]=new ArrayDeque<>();
if(adj[w]==null) adj[w]=new ArrayDeque<>();
if(!adj[v].contains(w))
adj[v].offer(w);
//当w包含v时形成闭环
if(adj[w].contains(v))
flag=true;
}
public String alienOrder(String[] words) {
int n=words.length;
if(n==1) return words[0];
mark=new boolean[26];
on=new boolean[26];
flag=false;
ans=new String();
adj=new ArrayDeque[26];
Set set=new HashSet<>();//存储出现的字母
//取相邻的两个单词
for(int i=1;iwords[i].length())
return "";
char[] chs1=words[i-1].toCharArray();
char[] chs2=words[i].toCharArray();
boolean find=false;//是否找到能确定顺序的两个字母
for(int j=0,k=0;j[] adj,int v){
mark[v]=true;
on[v]=true;
if(adj[v]!=null){
for (int w : adj[v]) {
if(!mark[w]){
dfs(adj,w);
} else if(on[w]){//已经标记的点,可能是之前遍历过的,也可能是本次路径上的
flag=true;
return;
}
}
}
on[v]=false;//回溯还原路径上点的状态
ans=(char)(v+'a')+ans;//当该点没有指向,或已经遍历完后面的点,该点入栈
}