NO.1割点与割边dfs(intk,intfather,intdepth){col[k]=GREY;dep[k]=depth;tot=0;for(每个与k相邻的点i){if(i!=father&&col[i]==GREY)low[k]=min(low[k],dep[i]);if(col[i]==WHITE){dfs(i,k,depth+1);tot=tot+1;low[k]=min(low[k],low[i]);if((k为根&&tot>1)||(k不为根&&low[i]>=dep[k]))k为割点;if(low[i]>dep[k])then(k,i)为割边;}}col[k]=BLACK;}例题分析例题分析例题分析例题分析NO.2强连通分量SCC应用SCC应用例题分析例题分析SCC应用Poi0106PeacefulCommission[和平委员会]输入n（党派数），m（不友好对数）及m对两两不和的代表编号其中1≤n≤8000，0≤m≤20000分析：初步构图假设4个组，不和的代表为：1和4，2和3，7和3，那么构图：先看这样一个结构：对于原图中的每条边AiAj（设Ai属于环Si，Aj属于环Sj）如果Si≠Sj，则在新图中连边：SiSj通过求强连通分量，可以把图转换成新的有向无环图，在这个基础上，介绍一个算法。算法中，如果存在一对Ai,Ai'属于同一个环，则判无解，否则将采用拓扑排序，以自底向上的顺序进行推导，一定能找到可行解。至于这个算法的得来及正确性，将在下一段文字中进行详细分析。深入分析：引理：原图具有对称传递性猜测1：图中的环分别对称推广1：新图中，同样具有对称传递性。分开来看，更加一般的情况，即下图：（说明：此图中Si'有可能为Si的后代节点）于是可以得到推广2：对于任意一对Si,Si'，Si的后代节点与Si'的前代节点相互对称。如果选择Si，那么对于所有SiSj，Sj都必须被选择。而Si'必定不可选，这样Si’的所有前代节点也必定不可选（将这一过程称之为删除）。由推广2可以得到，这样的删除不会导致矛盾。每次找到一个未被确定的Si，使得不存在SiSi'选择Si及其后代节点而删除Si’及Si‘的前代节点。一定可以构造出一组可行解。因此猜测2成立。另外，若每次盲目的去找一个未被确定的Si，时间复杂度相当高。以自底向上的顺序进行选择、删除，这样还可以免去“选择Si的后代节点”这一步。用拓扑排序实现自底向上的顺序。算法流程：