第 22 讲：深度优先搜索、拓扑排序与强连通分量

type DFS struct {
    g              *Graph
    color          []int // 0=白 1=灰 2=黑
    disc, fin      []int // 发现时间、完成时间
    parent         []int
    time           int
}

func (d *DFS) Run() {
    for u := 0; u < d.g.n; u++ {
        if d.color[u] == 0 {
            d.visit(u)
        }
    }
}

func (d *DFS) visit(u int) {
    d.color[u] = 1 // 灰：正在处理
    d.time++
    d.disc[u] = d.time

    for _, v := range d.g.adj[u] {
        if d.color[v] == 0 {
            d.parent[v] = u
            d.visit(v)
        }
    }

    d.color[u] = 2 // 黑：处理完毕
    d.time++
    d.fin[u] = d.time
}

func HasCycle(g *Graph) bool {
    color := make([]int, g.n)
    var visit func(int) bool
    visit = func(u int) bool {
        color[u] = 1
        for _, v := range g.adj[u] {
            if color[v] == 1 { // ⭐ 遇到灰色 = 后向边 = 有环
                return true
            }
            if color[v] == 0 && visit(v) {
                return true
            }
        }
        color[u] = 2
        return false
    }
    for u := 0; u < g.n; u++ {
        if color[u] == 0 && visit(u) {
            return true
        }
    }
    return false
}

func TopoSortDFS(g *Graph) ([]int, bool) {
    color := make([]int, g.n)
    order := make([]int, 0, g.n)

    var visit func(int) bool
    visit = func(u int) bool {
        color[u] = 1
        for _, v := range g.adj[u] {
            if color[v] == 1 {
                return false // 有环，无拓扑序
            }
            if color[v] == 0 && !visit(v) {
                return false
            }
        }
        color[u] = 2
        order = append(order, u) // ⭐ 完成时压入
        return true
    }
    for u := 0; u < g.n; u++ {
        if color[u] == 0 && !visit(u) {
            return nil, false
        }
    }
    slices.Reverse(order) // 完成时间的逆序就是拓扑序
    return order, true
}

func TopoSortKahn(g *Graph) ([]int, bool) {
    indeg := make([]int, g.n)
    for u := 0; u < g.n; u++ {
        for _, v := range g.adj[u] {
            indeg[v]++
        }
    }

    queue := make([]int, 0, g.n)
    for u := 0; u < g.n; u++ {
        if indeg[u] == 0 {
            queue = append(queue, u)
        }
    }

    order := make([]int, 0, g.n)
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        order = append(order, u)
        for _, v := range g.adj[u] {
            indeg[v]--
            if indeg[v] == 0 { // 所有前驱都排好了
                queue = append(queue, v)
            }
        }
    }
    if len(order) < g.n {
        return nil, false // ⭐ 有顶点入度永不为 0 ⟹ 存在环
    }
    return order, true
}

func Kosaraju(g *Graph) [][]int {
    // ① 第一遍 DFS，按完成时间入栈
    visited := make([]bool, g.n)
    order := make([]int, 0, g.n)
    var dfs1 func(int)
    dfs1 = func(u int) {
        visited[u] = true
        for _, v := range g.adj[u] {
            if !visited[v] { dfs1(v) }
        }
        order = append(order, u)
    }
    for u := 0; u < g.n; u++ {
        if !visited[u] { dfs1(u) }
    }

    // ② 构造反图
    rev := NewGraph(g.n)
    for u := 0; u < g.n; u++ {
        for _, v := range g.adj[u] {
            rev.adj[v] = append(rev.adj[v], u)
        }
    }

    // ③ 按完成时间逆序在反图上 DFS
    for i := range visited { visited[i] = false }
    var sccs [][]int
    var dfs2 func(int, *[]int)
    dfs2 = func(u int, comp *[]int) {
        visited[u] = true
        *comp = append(*comp, u)
        for _, v := range rev.adj[u] {
            if !visited[v] { dfs2(v, comp) }
        }
    }
    for i := len(order) - 1; i >= 0; i-- {
        if u := order[i]; !visited[u] {
            comp := []int{}
            dfs2(u, &comp)
            sccs = append(sccs, comp)
        }
    }
    return sccs
}

func Tarjan(g *Graph) [][]int {
    const unvisited = -1
    disc := make([]int, g.n)
    low := make([]int, g.n)
    onStack := make([]bool, g.n)
    for i := range disc { disc[i] = unvisited }
    var stack []int
    timer := 0
    var sccs [][]int

    var dfs func(int)
    dfs = func(u int) {
        disc[u], low[u] = timer, timer
        timer++
        stack = append(stack, u)
        onStack[u] = true

        for _, v := range g.adj[u] {
            switch {
            case disc[v] == unvisited:
                dfs(v)
                low[u] = min(low[u], low[v]) // 树边：继承孩子的 low
            case onStack[v]:
                low[u] = min(low[u], disc[v]) // ⚠️ 后向边：用 disc 而非 low
            }
            // v 已访问且不在栈上：跨到别的已完成 SCC，忽略
        }

        if low[u] == disc[u] { // ⭐ u 是 SCC 的根
            comp := []int{}
            for {
                v := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                onStack[v] = false
                comp = append(comp, v)
                if v == u { break }
            }
            sccs = append(sccs, comp)
        }
    }

    for u := 0; u < g.n; u++ {
        if disc[u] == unvisited { dfs(u) }
    }
    return sccs
}