模板整理: 图论---tarjan缩点/桥/割点

tarjan这算法没学好……气哦

目前掌握得还可以的只有缩点，

每次桥和割点只能手推。。还总是推错。

说实话也没什么难的啊。。

缩点,桥,割点之前的学习笔记

先是缩点，也就是强连通分量双联通分量这些东西。

只讨论强连通分量。

比较好理解，用DFN[u]表示到达u的时间（时间戳），

LOW[u]表示u及u的子树中能到达的最早时间戳.

那么想象一下，一个强连通分量，里面有某个u，

把u提起来，那么包含u的最大的强连通分量，

看上去一定是个像环一样的东西（其实复杂得多）

那么一定满足LOW[u]=DFN[u]，这个很好脑补吧。。

所以访问完u的所有子树之后判断

LOW[u]是否等于DFN[u]即可。

每次访问一个点的时候，将这个点入栈，

然后如果LOW[u]=DFN[u]，就一直从栈内弹出元素，

直到u为止即可。

双连通分量类似于强连通分量，但是对于无向边，

我们一般都是多加一条反向边的，

所以求双连通分量的时候，要注意不能走回它的父亲去

（除非这两个点之间有多条不同边）

//强连通分量缩点的模板
//instack[u]=1，当u在栈内；stk[]为存放元素的栈
//sccnum是强连通分量(scc)的个数，
//sz[i]是第i个scc含有的点数
//scc[i]表示（原图里）i号点属于第scc[i]个强连通分量
void tarjan(int u){
  DFN[u]=LOW[u]=++Time;
  instack[u]=1,stk[++top]=u;
  for (int i=head[u];i;i=E[i].next){
    int v=E[i].to;
    if (!DFN[v]){
      tarjan(v);
      LOW[u]=min(LOW[u],LOW[v]);
    } else
    if (instack[v]) LOW[u]=min(LOW[u],DFN[v]);
  }
  if (DFN[u]==LOW[u]){
    sz[++sccnum]=1;
    while (stk[top]!=u){
      instack[stk[top]]=0;
      scc[stk[top--]]=sccnum;
      sz[sccnum]++;
    }
    instack[stk[top]]=0;
    scc[stk[top--]]=sccnum;
  }
}      

然后是桥，桥的定义大致可以理解为：

假如去掉了(u->v)这条边，那么将会产生两个连通块(也就是u和v不再连通)

假设(u->v)是桥，那么u满足什么性质呢？

同样看作把u拎起来，那么对于u的所有儿子（也就是所有的v），

儿子能到达的最早时间戳（也就是LOW[v]）一定不会越过u，