案例一
最开始看到这道题，直觉告诉我可以用魔改版的 BFS 解决：只要生成两种颜色的邻接表，BfS 的奇数步用一种颜色，偶数步用另一种颜色，就可以了。但是尝试编码后，我发现两种颜色可以一起形成环，导致同一个节点能够被访问超过一次，比如下图的用例中，通往节点 4 的符合题意的路径，就允许节点 1 被重复访问：
这个用例让我的大脑陷入了死机，所以我决定看官解：
不知道各位小机灵鬼看了官解这几段文字是啥感觉，反正我是读了不下 10 次，依然死都读不懂，并且一点也没有被震撼到哈哈哈哈。
然后看了其他几位大佬们的题解，依然是两眼一抹黑：
大佬们讲的要不比较抽象，要不太简短，要不文字和代码混合，加上我这几天吃抗抑郁药变傻了，真的是好绝望。
然后我突发奇想打开了英文版的官解（虽然我的英文很烂），甚至还没有通读，在遇到下面这句话的时候，突然就豁然开朗了：
In contrast to a normal traversal where each node is visited only once, here a node can be visited at most twice. It can be visited once from a red edge and once from a blue edge.
也就是说，这道题的关键就在于：和普通的 BFS 每个节点只能被访问一次不同，这道题中每个节点最允许被访问最多两次，一次是通过红色边访问，另一次是通过蓝色边访问。
最多两次，这个太关键了。
把握了这个关键，我立刻调整了自己的代码，很快就 AC 了：
/*阅读英文题解后，灵机一动 AC 了的版本*/
class Solution {
private int inf = 0x3f3f3f3f;
public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
List<Integer>[] redAdt = calcAdt(n, redEdges); // 红色邻接表
List<Integer>[] blueAdt = calcAdt(n, blueEdges); // 蓝色邻接表
int[] ret = bfs(n, redAdt, blueAdt); // 红蓝红蓝红……
int[] ret2 = bfs(n, blueAdt, redAdt); // 蓝红蓝红蓝……
for (int i = 0; i < ret.length; i++) {
ret[i] = Math.min(ret[i], ret2[i]);
if(ret[i] == inf)ret[i] = -1;
}
return ret;
}
private int[] bfs(int n, List<Integer>[] adt1, List<Integer>[] adt2) {
Queue<Integer> queue = new LinkedList<>();
int[] ret = new int[n];
Arrays.fill(ret, inf);
queue.offer(0);
ret[0] = 0;
boolean[] visited1 = new boolean[n];
boolean[] visited2 = new boolean[n];
visited2[0] = true;
int step = 0;
while (!queue.isEmpty()) {
List<Integer>[] adt = step % 2 == 0 ? adt1 : adt2;
boolean[] visited = step % 2 == 1 ? visited1 : visited2;
int size = queue.size();
while (size-- > 0) {
int u = queue.poll();
ret[u] = Math.min(ret[u], step);
for (Integer v : adt[u]) {
if(visited[v])continue;
visited[v] = true;
queue.offer(v);
}
}
step++;
}
return ret;
}
private List<Integer>[] calcAdt(int n, int[][] edges){
List<Integer>[] adt = new List[n];
for (int i = 0; i < n; i++) {
adt[i] = new ArrayList<>();
}
for (int[] e : edges) {
adt[e[0]].add(e[1]);
}
return adt;
}
}这个故事说明，长篇大论、图文并茂，远没有点出关键重要。一句关键的描述，往往能让人豁然开朗。
案例二
这道题更悲催，直接没有官解（截止当前的 2023-02-17）。
看了各位大佬的非官解，再一次没有看懂，绝望 again：
看了一下题目最下面的提示，依然看不懂：
这个提示的意思是：把图当成无向图，进行一次 dfs；如果遇到一条向前的边，你需要把它反过来。
现在我已经接触这道题来了，这句话自然很容易理解，但是刚看到时，真的是云里雾里：题目给的明明是有向图，让我当成无向图是什么鬼？farward direction 是什么鬼？相对于什么东西 farward?
然后我有看了英文官方题解，当看到下面蓝色里的字和图时，我立刻恍然大悟：
英文题解很长，但是看到这里，我已经有思路了，后文没有继续看，尝试编码了三个版本，都后很快 AC，甚至比英文官解还快一点：
/*dfs 递归版*/
class Solution {
public int minReorder(int n, int[][] connections) {
List<Integer>[] undirectedAdt = new List[n]; // 把树作为无向图的邻接表
List<Integer>[] directedAdt = new List[n]; // 把树作为有向图的邻接表
for (int i = 0; i < n; i++) {
undirectedAdt[i] = new ArrayList<>();
directedAdt[i] = new ArrayList<>();
}
for (int[] e : connections) {
undirectedAdt[e[0]].add(e[1]);
undirectedAdt[e[1]].add(e[0]);
directedAdt[e[0]].add(e[1]);
}
// 从 0 开始，按照无向图的方式遍历图，可以 BFS，也可以 DFS，这里用 DFS
int[] ret = new int[1];
boolean[] visited = new boolean[n];
bfs(undirectedAdt, directedAdt, 0, visited, ret);
return ret[0];
}
private void bfs(List<Integer>[] undirectedAdt, List<Integer>[] directedAdt, int u, boolean[] visited, int[] ret) {
visited[u] = true;
for (Integer v : undirectedAdt[u]) {
if(visited[v])continue;
bfs(undirectedAdt, directedAdt, v, visited, ret);
if(directedAdt[u].contains(v))ret[0]++;
}
}
}上面的 dfs 迭代版，是对学习的小技巧「DFS，但是用迭代不用递归」现学现卖🤣
不算结语的结语
防喷预判
这是最后一次贴「防喷预判」文字了，这样真的有点累，但我又确实怕被喷。本文：
- 只是日常分(灌)享(水)、记录。本人社恐，发帖有的时候有交流感，会开心一点。
- 不是为了秀自己的英语，本人英语底子可以，但词汇贫乏，水平很烂，还在恶补。
- 不存在 XXX 的月亮更圆的问题。英文中文，都是工具，能让我学到知识的都是好工具。
- 不内涵任何大佬。加这一点，是发现文中贴了部分大佬的题解截图，故有此担心。我只是自己一时没看懂，不代表大佬们写的不好。过去、现在、未来，我都不会内涵人，也不喜欢内涵任何人。
- ……
有扣友说，每次看见我发的帖子，都感觉我是要搞事情、要整活。我现在真的有心理阴影了。我表示真的很无奈。相信我，我不喜欢搞事情。
上次也有位扣友说，「老宋挺真诚的」，看到这句话我突然就绷不住了：
来自陌生人的善意，真的会让人开心。
我的原则一直是，如果我说错了，别人指出来，我会调研、改正、讨论。但如果上来冷嘲热讽、直接开喷，我也可能在情绪差的时候刚回去。
写到这里，我突然产生了一种诡异的好奇心，不知道这次扣友会找到什么新奇的 diss 角度🤣。我想应该不会有了。
吃药之后扯几句抑郁症
最后，有朋友问我抑郁症的事情，扯几句抑郁症。
抑郁症真的不是人内心不够坚强，是病，是病，是病！！！是大脑神经系统产生了生理、生化改变的病，虽然这种病有心理方面的诱因。抑郁症和抑郁情绪的区别，是前者持续的时间很长，可以达到数天，甚至数周、数月，是一种弥散式的心境；而抑郁情绪，一般来的快，去的也快。
得了抑郁症，一定要遵医嘱，要认真吃药，不可以私自停药。
抑郁症最大的特点，是会夺走患者全部的激情，让患者变的对任何事情都提不起兴趣。抑郁患者可以在屋子保持一个姿势里躺一天，可以不吃饭不洗脸不洗澡不打扫卫生，任何一件小事都会让患者感到疲惫无比。所以，抑郁患者，真的也不是懒。有的抑郁患者表面上看起来比较阳光，甚至幽默风趣、舌灿莲花，完全看不出抑郁来。
我的抑郁症，其实是被自己耽误了。虽然我是学心理的，但是我讳疾忌医，不愿意承认自己有病，只是觉得自己不够坚强。现在回想，其实十几年前就有抑郁征兆，最近五六年已经很明显了。今年大年初二的时候，严重地发作了一次，也是这一次，让我下定决心去看大夫。
就我个人而言，生活几乎感觉不到快乐。偶尔会突然记起一些过去的事情，然后脑子里像过电影一样不断回忆，然后陷入很深的悲伤无法自拔。平日，在这种突发的悲伤之外，主要表现还是无精打采、病恹恹的。
此外，根据我学心理的经历，以及看病的经历，我觉的精神科的大夫，和心理医生，在国内的区别还是很大的。如果你也有抑郁症，去看精神科大夫时，他们可能只会像对普通病人一样给你诊断、开药，你不应该寄希望于精神科大夫会成为你的倾诉对象；他们甚至可能会反复打断你，让你觉得很粗暴，让你觉得他很不耐烦。其实这是医疗体系的整体特点，大概公立医院的大夫都很忙。感兴趣的读者可以看一下这个知乎帖子：医生只花 5 分钟就完成了从诊断到治疗方案给出，科学吗？
我现在已经吃药快两周了，吃的是阿立哌唑和曲舍林。阿立哌唑的副作用比较大，会导致出现静坐不能的现象：我心中毫无波澜，但是腿一直想动，很想跑到楼下不断走路，如果在屋子里，会不由自主地无目的地乱走，如果在床上，会不断地来回打滚，仿佛我变成了多动症儿童。
如果强迫自己坐在电脑前，会感觉特别难受，根本无法集中注意力。因为静坐不能的副作用，最近刷题量直线下降。一个图论的基础题单，刷的我七荤八素。
除了静坐不能，还有一些别的副作用，就不写了。
现在遵医嘱，尝试把药量减半了，副作用轻了一些。希望我能尽早扛过这段副作用期。
刷题是真的快乐，我会继续刷。
