tarjan复习小结

虽然是复习，但还是学到许多。

tarjan求强连通分量

基础知识

过程中遇到四种边
1>树枝边：(dfs)搜索树上的边满足边((u,v) ,v)不在栈中 (u)为(v)的父节点
2>前向边：与(dfs)方向一致祖先指向子孙 ~~没什么用~~
3>后向边：与(dfs)方向相反子孙指向祖先满足边((u,v)). (v)在栈中，(u)为(v)的祖先节点
4>横叉边：从某个结点指向搜索树中另一子树中某结点的边满足边((u,v)), (v)在栈中 (u)不为(v)的祖先节点

定义两个数组(dfn)和(low)，(dfn[x])表示(x)节点是第几个被遍历到的。(low[x])表示(x x)以及它的所有子树的出边的(dfn)的最小值,由定义可以得出：

如果((u,v))是树枝边 (low[u]=min(low[u],low[v]))
如果是横叉边或后向边 (low[u]=min(dfn[v],low[u]))

当结点(u)的搜索过程结束之后，若(dfn[u] == low[u]) 则以(u)为根的搜索子树上所有还在栈中的结点，是一个强连通分量，可退栈，为什么呢？？？？
~~我也不知道~~

通俗的说，若(u)为强连通分量的根，那么它的子孙中的最高祖先应该是它本身。

算法流程

数组的初始化，当首次到达(u)这个点时，更新(low)与(dfn)的值，将(u)入栈
更新(low[u])
如果((u,v))是树枝边 (low[u]=min(low[u],low[v]))
如果是横叉边或后向边 (low[u]=min(dfn[v],low[u]))

如果u的子树全被遍历完，(low[u] == dfn[u])那么退栈，退到(u)退出，这些退出的元素就是一个强连通分量。

因为图有可能有好几个部分，也就是说，(tarjan)图不连通。那么我们还要继续搜索，直到所有点都被遍历

code

void tarjan(int x) {
    low[x] = dfn[x] = ++cnt, sta[++top] = x, vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (!dfn[to]) tarjan(to), low[x] = min(low[x], low[to]);
        else if (vis[to]) low[x] = min(dfn[to], low[x]);
    }
    if (dfn[x] == low[x]) {
        num++;
        while (x != sta[top + 1]) {
            vis[sta[top]] = 0;
            top--;
        }
    }
}

for (int i = 1; i <= n; i++)
    if (!dfn[i]) tarjan(i);

模型建立

其实就是缩点，要不然也没别的用处。

因为每一个强连通分量中的点都是相互可达的，我们可以将当前这个强连通分量缩成一个点，这个点的权值由题目来定（通常会有强连通分量中的点权和或者点权的最小值）

我们用到染色的思想，因为退栈的时候退栈的所有元素都是同一个强连通分量中的，所以我们可以在这个时将所有的点都染成同一种颜色，同时处理缩完点之后点的权值。

code

void tarjan(int x) {
    low[x] = dfn[x] = ++cnt, sta[++top] = x, vis[x] = 1;
    for (int i = head[x]; i; i = edge[i].next) {
        int to = edge[i].to;
        if (!dfn[to]) tarjan(to), low[x] = min(low[x], low[to]);
        else if (vis[to]) low[x] = min(dfn[to], low[x]);
    }
    if (dfn[x] == low[x]) {
        num++;
        while (x != sta[top + 1]) {
            vis[sta[top]] = 0;
            col[sta[top]] = num;
            val[num] += a[sta[top]];
            top--;
        }
    }
}

例题

间谍网络
 稳定婚姻
 消息扩散
 HXY烧情侣
 受欢迎的牛
 校园网
 最大半连通子图
 网络协议
 消息的传递
 间谍网络