图论 发表于 2018-09-27 求割边求错了QWQ写一篇跟tarjan有关的总结 有向图:求强连通分量:重边、自环都不影响求解,记录fa,要写栈求割边:未定义割边,要根据题目转化成无向图做(可能吧)求割点:未定义割点,要根据题目转化成无向图做(可能吧) 无向图:求割边:自环无影响,重边有影响,要记录是从哪条边来的,而不是记录fa,不要写栈dfn[x]<low[x],所以不能用fa更新求割点:自环、重边无影响,不用记录fa,不要写栈。注意根节点。dfn[x]<=low[x],所以可以用fa更新