Category Archives: 连通图

51nod 1445 变色DNA (分析,最短路)

有一只特别的狼,它在每个夜晚会进行变色,研究发现它可以变成N种颜色之一,将这些颜色标号为0,1,2&#8230 …

51nod 1076 2条不相交的路径 (分析,Tarjan)

给出一个无向图G的顶点V和边E。进行Q次查询,查询从G的某个顶点V[s]到另一个顶点V[t],是否存在2条不相 …

HDU 4685 Prince and Princess (二分匹配,强联通)

n个王子和m个公主,王子有喜欢的公主,公主可以嫁任意王子,求每个王子能选的公主有哪些能使得每个王子都能匹配到公 …

HDU 4635 Strongly connected (强联通缩点)

一个有向图,问最多添加多少边使得图变成简单且不强联通的图。 只要处理缩点完的图,形成{X}-{Y}的形式,枚举 …

HDU 4612 Warm up (双连通缩点,树直径)

一个无向图,问在添加一条边如何使得图的桥变得最少,如果将图双连通缩点之后就会形成一棵树,树上的每个边都是原图的 …

POJ 3177 Redundant Paths (双联通缩点)

一个无向图,求最少添加多少边使得任意一个点都能够有两个临接节点可以走。 先把重编盘掉,双连通缩点,生成了一棵树 …

POJ 3694 Network (割边,LCA)

一个无向图,给出q个询问,每个询问将u, v两点连边,然后求现有的割边(桥)的数量。 首先Tarjan找出桥, …

Tarjan-点连通、边连通、强连通

点连通和边连通写法有一个细微的差别,点连通不用考虑重边带来的影响!但是边连通重边会导致原本是桥的变成不是桥,但 …