水晶铭刻之旅一开始是想构造并查集然后每个并查集中选其最小值然后加和是结果但必须要求形成回路即使节点互联也可能无法一次走完所有节点并回到原点比如九点、九宫格从任意一点出发都无法经过其它所有节点必然要切分出8个点和一个点所以切分回路最终结果是切分出所有回路中最小值的加和如何达到并求出所有可能的切分方案AI题解SCC求解SCC问题定义那如何求解SCC以及什么叫求解SCC是求所有可能的SCC切分方案吗还是某一种比如{1234}四个点两两之间都可达那么最大的SCC是1234但12341234等也是可行的切分方案所以如何定义求解SCC对于九宫格的九个点它们每个点之间都两两可达但是其并不能构成一个环那这九个点是否还构成SCC那么如何求解SCC即对于给定的图求出极大的SCC切分图Kosaraju算法什么叫源SCC汇SCC第一遍DFS先后序求得图中各点结束时的时序第二遍DFS反向是为什么以及没理解与第一次DFS之间的关系又或者没理解第一次DFS的意义在哪即知道结束时间的排序有什么用第二遍又为什么要反向遍历最终结果又是怎么来的源 SCC 和汇 SCC第一遍 DFS 到底在求什么不过dfs怎么保证得到的是拓扑序比如1234之间是一个环即1-2-3-4但是对于2如果延申出一个到5的边那么在dfs时先是1然后2到2时如果先到3那完成时间就是{4,3,5,2,1}如果先到的是5那就是{5,4,3,2,1}而SCC的切分是{1,2,3,4}和{5}即A-B对于后者汇SCC即{5}是都比源SCC早结束的但是对于前一种可能就不是第二遍为什么要反向图我现在理解的给定一个图a,b,c,d,e,f等第一次DFS得出一个完成时间顺序后貌似可以视为完成一次缩点成为{A,B,C}即满足max finsh(A)..B..C然后再反向如果是环的话那么依然是环即A,B,C内部依然可互联但因为反向了所以是{C,B,A}A就不能到BB也不能到C了并且因为 max finsh(A)的限制所以对于dfs得到的遍历序列中第一个数一定是SCC A中的点然后由于反向的限制A的点一定不可达B所以就可以不断拨出A,B,C中的点不过既然第二遍是依据Max finsh(A)的性质那能否反其道而行之即既然A-B-C那么C也一定最先完成且C也无法到B,B无法到A那每次就不断取最先完成遍历的点它一定是汇SCC当中的点这样也就省去了构造反转图的开销就是说如果不构造反图那么要求最先完成的点一定属于汇SCC但这并不一定成立因为对于A-B的结构对于A和B的临界点可能先完成A的环再到B这样最先完成的就是A中的点而不是B的点所以以此为基础的方法根基上不可行除非对于A-B的结构在临界点选择时能保证选择的点一定是B而对于max finish就一定是满足A-B-C的即从第一遍DFS得到的序列第一个遇到的点一定是源SCC的把它所有的点抛出后下一个遇到的点也一定是新源SCC的K算法实现题解先是在输入时构造好反向图然后是第一次DFS目的是得到遍历序列第二次DFS依据第一次的遍历序列标记每个点所处的SCC最后遍历每个点检查每个点的值与所处的SCC统计好每个SCC当中的最小值与最小值数量最后返回结果此外在第一次DFS时应该是必须要求起点在源SCC当中的否则无法到达但对于输入的图如何在第一次DFS之前就知道源SCC比如A-B-C在第一次DFS时如果先访问C再访问B最后再到A由于单边的存在第一次的序列可能就是{C,B,A}然后在第二次DFS时因为是反向图所以就有C-B-A构成那此时依据第一次DFS的序列是否会认为C是源SCC然后在第二次时错误连着访问B,A将其视为一整个大环即C,B,A整体是一个SCC得到错误结果实际上不会出错就是说神奇的是即使先访问的是C但其最终得到的序列依然是最先完成的序列即C先完成B其次A最后是Max Finish,而非每个点)如果是B先那么因为B-C的存在所以依然还是C,B,A如果是A那么也还是C,B,A所以在dfs时除非真的每边才会有无关的顺序否则一定是按最先完成的顺序排列的DEBUG代码输入反向建图第一次dfs函数栈第二次dfs统计结果对于后序遍历如何用栈来实现但是在代码实现时该如何实现这个特性呢即如果是按入栈时的顺序来标记处理次序即思路是越早被处理的点应该越晚出栈的思想这个应该是会遇到上面的问题的就应该是按出栈时的顺序来标记次序但这样又什么时候该出栈一般是先入栈并把它的所有孩子加入到栈中然后开始循环不断取出栈头然后处理但这时取出栈头算出栈吗?还是说是没孩子的时候才算真正出栈有孩子的时候不出栈那Vis标记就应该是在入栈时就直接标记什么是Tarjan算法什么是二分图什么是哈密顿环
