對於Tarjan縮點的復習

今天一天之内兩場比賽都考到了Tarjan縮點。（可見其之重要性）

於是，我們不如來復習一波。。

Tarjan是一位非常操蛋帅的人，发明了大量的算法，什么并查集求LCA啊，什么SPLAY啊...不过最出名的还是他发明的缩点算法了

首先，什么叫缩点呢？我们需要先理解什么是强连通分量

强连通分量指的是：在一个有向图中，强联通分量的点可以互相到达，如在下图中，一块黄的就是一个强联通分量

直接上代码注释好了：

int DFN[maxn],LOW[maxn],index;//序号及环开头的序号
int S[maxn],top;//手写栈
bool ins[maxn];//是否进栈
int col[maxn],numc;//染色
void Tarjan(int u){
    DFN[u] = LOW[u] = ++index;
    S[++top] = u;//进栈
    ins[u] = true;
    for(int i = head[u];i;i = E[i].nxt){
        int v = E[i].v;
        if(!DFN[v]){
            Tarjan(v);
            LOW[u] = min(LOW[u],LOW[v]);//找爸爸（环开头）最小的
            }
        else if(ins[v]){
            LOW[u] = min(LOW[u],DFN[v]);//判断谁是爸爸
            }
        }
    if(DFN[u] == LOW[u]){//发现更新完一轮自己是爸爸
        numc++;
        while(S[top + 1] != u){
            col[S[top]] = numc;//出栈，染色
            ins[S[top--]] = false;
            }
        }
    }

关于Tarjan缩点的技巧

我们分两种情况：

1.题目直接考Tarjan（重点）

这种情况一般是直接考缩点，通常和图论的知识连用，而又以出度和入度最为常见

首先如果原图是一个无向又环图，我们是没办法对其进行某些操作的（比如可以重复走一条路但是点权只加一次这类的），因为要重复访问，所以DFS就毫无用武之地了，这时候我们就需要又Tarjan，在跑Tarjan的时候处理环的某些性质（如点权什么的），在建新图，就可以在新图上进行dp或者遍历了。

2.题目考其他

这里不再赘述，Tarjan就是一个辅助作用，把有环图缩为无环图，就可以使用一些算法解决问题了

最後，祝大家國慶愉快！（czy_轉過身去繼續努力學習）

---

• Next Post →