双联通分量学习笔记

双联通分量学习笔记

刷了一些题

• hdoj 3394

  • 题意：问有多少边在多个环上，有多少边不在任一个环上。（环是简单环）
  • 题解：环肯定存在某点双联通分量上。
    • 点数>边数：该双联通分量只有一条边。
    • 点数=边数：只有一个环。
    • 点数<边数：多个环。
  • 实现：把每个双联通分量拉出来数边数。

• UVAlive 5135

  • 题意：在给定的图中建安全点，问至少需要建多少个，使得任一个点被删掉，其他点都能和某个安全点联通。输出个数和方案数。
  • 题解：如果一个点双联通分量有一个割点，那么它内部肯定要建安全点。其他都不用。特判只有一个点双联通分量的情况。

• poj 1523

  • 题意：求割点，以及该割点删除后图还有几个联通块。

• poj 2942

  • 题意：问有多少个点不属于任一个奇环。
  • 题解：染色法判点双联通分量的奇环。
  • 实现：把每个双连通分量拉出来。

• poj 3694

  • 题意：给出一个图，每次询问建立在前一次基础上。每次询问加一条边后还有多少桥。
  • 题解：直接在搜索树上做朴素的lca，缩点用并查集。

• poj 3352 & poj 3177

  • 题意：最少加几条边使得给定的图满足任意两点之间都有两条不重合的路。
  • 题解：任意两点之间都有两条不重合的路<=>边双联通。答案是(叶子节点+1)/2。