图论连通性

无向图

• 割点：删除x和与x相连的边，图不再连通，x为割点
• 割边：删去该边e，图不再连通，e为割边
• 点双连通分量：其本身不存在割点，但可以有原图的割点（此时在这个点双中就是普通的点），极大图，一个点双中可以有多个原图的割点
• 边双连通分量：其本身不存在割边，极大图
• 点双不具有传递性，边双具有传递性((x,y),(y,z)=>(x,z))

  Tarjan

  •  时间戳dfn：访问到的时间
  • 返祖边：搜索树上连向其祖先节点的边
  • 由于搜索树结构，不存在横向边（连向同层节点的边）
  • low[u]定义：u和以u为根的子树通过返祖边（包括树边和非树边）能连到的最小的dfn
  • 若是一条树边：low[u]=min(low[v[,low[u])
  • 若是一条非树边：low[u]=min(low[u],dfn[v])

    求割点

    • 割点满足：其儿子的low[v]>=dfn[u]，即没有儿子跨过u，儿子与u相连只有树边
    • 对于根要判断儿子个数大于1
    • 可以走反向边
    • 特判为根且搜索树上只有一个儿子，此时注意重边
    • 求a,b间的割点，tarjan(a)判断如下

      if(low[v]>=dfn[x]){
          if(x!=a&&x!=b&&dfn[x]=dfn[u]，则出栈直到v出，此时出栈的所有点和v是一个点双

    • 每个点双，每个点都在一个环上，若点双有奇环，则所有点都在奇环
    • 判奇环，二分图黑白染色

      求割边

      • 割边满足： 一条边只走一次，v没有另一条边到达u（父亲）即low[v]>dfn[u]
      • 可以避免重边

         求边双

        • 一边只走一次，若low[u]==dfn[u]（除了树边，没有其他到树上祖先的边），则为边双

          点双缩点连图

          • 割点单独为一个点，每个点双除割点，缩成一个点
          • 割点向其所在的点双连边

            边双缩点连图

            • 每个边双缩点，用桥相连 

              缩点连图

              • 转为无向无环图 

                有向图

                • 强连通：图中存在路径u--->v和v--->u
                • 弱连通：图中只存在路径u--->v或v--->u
                • 强连通分量：该子图中对于任意一点对，存在路径u--->v和v--->u，极大图

                  Tarjan

                  • 时间戳dfn
                  • low[u]为u和以u为根的子树中能连到的还未出栈的最小dfn
                  • 访问到则入栈
                  • dfn[u]=low[u]，即到该点往上不会有强连通（有向边），
                  • 出栈直到u出栈，此时出栈的点为一个强连通分量

                     强连通缩点

                    • 将有向图，转为有向无环图
                    • 之后可以考虑入度出度，topu排序dp
                    • 注意会有重边，所以缩点连边时要判断是否已经连上，不要重复计算入度出度
                    • 求加入最少的边变成一个强连通，先缩点

                      int a=0,b=0;
                      for(int i=1;i