博文
求割顶－－ZJU1311(2007-04-18 15:17:00)
摘要：
求割点（关键点）
首先，对于单独的一个点，或者2个点，我们不予考虑，因为我们没法认定。
分情况：
如果待确定的点不是搜索树的根节点，那么关键点可以认为是这样的点V，他的子孙节点中存在一个节点P，从P出发继续向下拓展（也就是不再走已经走过的边，而是向下兜圈子，然后通过某个后向边回到前面已经访问过的点，这里可以看出后向边的价值，后向边在dfs中是不允许扩展的，但是我们说的“兜回到祖先”就是通过某个后向边实现的）dfs不能达到V的祖先，事实上，只要有任意一个子孙节点符合这个特性，那么v就是关键点，因为原本子孙和祖先是连通的，删除它之后，他的子孙至少无法走到他的祖先（包括它的兄弟姐妹。。。）
如果是根节点，他如果只有一个子树，那么他不是关键点，如果有多于一个的子树，那么他必然是关键点
具体实现：
具体实现是这样的，我们定义一个点上的函数dfn(v)，表示v这个点在dfs过程中第一次访问的顺序，然后，为了达到上面的定义，我们再定义一个点上的函数low(v)，low(v)表示从v出发，继续向下拓展搜索，所能达到的最早的点，也就是dfn最小的点
显然，low(v)有：
low(v)=min(dfn(v),low(s),dfn(w))
其中，s是所有儿子节点，w是v的后向边
割顶：
连通图G的一个顶点子集V，如果删除这个顶点子集和它所附带的边后，图便不再连通。则称V是G的割顶集。
最小割顶集中顶点的个数，称为G的连通度。连通度等于1时，割顶集中的那个顶点叫做割顶。
注意：完全图的连通度为总顶点数－1；
牵一发而动全身的点称为割点
边连通度：
连通图G的一个边子集E，如果删除边子集的边后，图便不再连通，则称E是G的桥集。
含有最小边数的桥集的边数|E|称为G的边连通度。|E|＝1时，E中的边叫做桥。
注意：规定不连通图的边连通度为0；完全图的边连通度为总顶点数－1；
连通图的两个特征：
1 连通度<=边连通度<=顶点数
2 顶点数大于2的2连通图的充分必要条件是任两个顶点在一个圈上.(没搞明白)
块的概念：
没有割点的连通子图，这个子图中的任何一对顶点之间至少存在两条不相交的路径，或者说要使两个站点同时发生故障
至少两个站点同时发生故障，这种二连通分......
ACM竞赛之新人向导(2007-04-18 15:12:00)
摘要：ACM竞赛之新人向导
2007-04-05 20:49
原创：怒火之袍
2003年4月29日
我们学校的计算机学院从去年起开始组织学生参加世界上最具权威性的大学生程序设计竞赛——ACM/ICPC。从这学期开始，学院计划有组织地进行训练和讲座，以帮助大家在有限的时间内尽可能多地提高自己的能力，这对有兴趣投入数据结构与算法研究的同学来说无疑是一件好事。但是，刚刚接触信息学领域的同学往往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。
一、语言是最重要的基本功
无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降低程序的执行效率。
接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。
而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。
C......