Garbage fish

主题

00:00:00
Garbage fish2024-10-12图论
1010
3.9m

Tarjan（割点 & 割边 & 点双 & 边双）& Kosaraju & 欧拉路 笔记 ​

迟到整整一年的笔记。2023/9/23 学的，2024/10/11 才写笔记，所以写的超水。

Tarjan ​

Tarjan 就是一种比较高级的 DFS，它按照深搜遍历的顺序打上时间戳，并维护一个 lowu 表示不经过打时间戳的深搜时 u 点的父亲，能回到时间戳最小的地方是多少。同时容易发现 Tarjan DFS 出来的构成一棵树。

cpp
void dfs(int u, int fa) {
    dfn[u] = low[u] = ++idx;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (!dfn[v]) {
            dfs(v, u);
            low[u] = min(low[u], low[v]); //（1）
        } else if (dfn[v] < dfn[u] and v != fa)
            low[u] = min(low[u], dfn[v]); //（2）
    }
}

很好理解，（1）处的出边 v 一定不会是 u 的父亲，因为 u 的父亲已经被打上 dfn 标记了，而（2）处有判断 v≠fa。

割点 ​

定义：一张无向图中，删去某个点整个图就不连通，这个点就是割点。

如果有一个点 u，它在 Tarjan 树上有一个子节点 v 满足 lowv≥u，那么这就是一个割点。因为无论怎么走 v 也最多只能往上走到 u，把 u 一删 v 就和 u 上面的断开了。

对于根节点，如果它有超过 1 个子树，那么把它删掉整个图也不连通了。

割边 ​

定义：一张无向图中，删去某条边整个图就不连通，这条边就是割边。

和割点差不多，不过 lowv≥u 变成了 lowv>u。v 不经过和它父亲 u 的连边连 u 这个位置都到不了了，把 (u,v) 这条边删了就不连通了。

而且没有根节点的判断了。

点双连通分量 ​

定义：一张无向图的某张连通的子图不存在割点，简称点双。

如果出现了割点，只是删去割点后，割点上方和（割点及割点下方）无法连通而已，所以割点及割点下方就是一个点双，将这个点双“删去”，接着做。

“删去”的操作用栈很好维护，假设一开始是空栈，每个点遍历到了就丢进栈里，如果遇到 lowv≥u，按照 Tarjan 先 DFS 后求 low 的顺序，v 下方已经全部遍历了一次，所以这下面的点也全都进栈了，把 v 到栈顶的全部丢出去存进一个点双里，u 是割点，也属于这个点双，但可能它还属于别的点双，暂时不需要出栈，这样子 v 及下方就被“删去”了。

边双连通分量 ​

定义：一张无向图的某张连通的子图不存在割边，简称边双。

这个更简单了，不用像点双一样担心那个割点到底算进哪个点双，直接把割边全部求出来再跑一遍别走割边就好了。

Kosaraju ​

求 SCC（强连通分量）的。

SCC 定义：一张有向图的某张连通的子图中的点可以互相到达。

这个最简单了，还好记，建正图跑 dfs 倒序全部进栈，接着从栈顶开始取，取出来的点在反图上跑，能跑到的地方而且还没被别的 SCC 占领的就是同一个 SCC，证明我不会。

cpp
void dfs(int u) {
    if (vis[u])
        return;
    vis[u] = true;
    for (auto v : g[u])
        dfs(v);
    st.push(u);
}
void dfs2(int u) {
    if (scc[u])
        return;
    scc[u] = scccnt;
    sz[scccnt]++;
    for (auto v : rg[u])
        dfs2(v);
}
void kosaraju() {
    for (int i = 1; i <= n; i++)
        dfs(i);
    while (!st.empty()) {
        if (!scc[st.top()]) {
            scccnt++;
            dfs2(st.top());
        }
        st.pop();
    }
}

欧拉路 ​

定义：可以不重不漏一次走完整张图的路径。

  • 无向图：
    • 图是连通的。
    • 欧拉路：2 个奇数度数顶点。
    • 欧拉环：没有奇数度数顶点。
  • 有向图：
    • 图是 SCC。
    • 欧拉路：最多有 1 个顶点出度比入度大且只大 1，是欧拉路的起点。最多有 1 个顶点入度比出度大且只大 1，是欧拉路的终点。
    • 欧拉环：每个点的入度和出度相等。
最近更新