2022-05-16：A -> B，表示A认为B是红人，
A -> B -> C，表示A认为B是红人，B认为C是红人，规定“认为”关系有传递性，所以A也认为C是红人，
给定一张有向图，方式是给定M个有序对(A, B)，
(A, B)表示A认为B是红人，该关系具有传递性，
给定的有序对中可能包含(A, B)和(B, C)，但不包含(A,C)，
求被其他所有人认为是红人的总数。
测试链接 : http://poj.org/problem?id=2186，
注册一下 -> 页面上点击"submit" -> 语言选择java，
然后把如下代码粘贴进去, 把主类名改成"Main", 可以直接通过。
强连通分量练习题目。

答案2022-05-16：

tarjan算法。
出度为0的有两个或两个以上，不存在顶级大红人。
只有一个集体，那么这个集体有多少个元素就有多少个红人。

代码用golang编写。代码如下：

package main

import "fmt"

var sc = []int{3, 3, 1, 2, 2, 1, 2, 3}
var ii = 0

func next() int {
    ii++
    return sc[ii-1]
}

func hasNext() bool {
    return ii < len(sc)
}

func main() {
    for hasNext() {
        n := next()
        m := next()
        edges := make([][]int, 0)
        for i := 0; i <= n; i++ {
            edges = append(edges, make([]int, 0))
        }
        for i := 0; i < m; i++ {
            from := next()
            to := next()
            edges[from] = append(edges[from], to)
        }

        connectedComponents := NewStronglyConnectedComponents(edges)
        sccn := connectedComponents.getSccn()

        if sccn == 1 {
            fmt.Println(n)
        } else {
            dag := connectedComponents.getShortGraph()
            zeroOut := 0
            outScc := 0
            for i := 1; i <= sccn; i++ {
                if len(dag[i]) == 0 {
                    zeroOut++
                    outScc = i
                }
            }
            if zeroOut > 1 {
                fmt.Println(0)
            } else {
                scc := connectedComponents.getScc()
                ans := 0
                for i := 1; i <= n; i++ {
                    if scc[i] == outScc {
                        ans++
                    }
                }
                fmt.Println(ans)
            }
        }
    }
}

func getMax(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

type StronglyConnectedComponents struct {
    nexts     [][]int
    n         int
    stack     []int
    stackSize int
    dfn       []int
    low       []int
    cnt       int
    scc       []int
    sccn      int
}

// 请保证点的编号从1开始，不从0开始
// 注意：
// 如果edges里有0、1、2...n这些点，那么容器edges的大小为n+1
// 但是0点是弃而不用的，所以1..n才是有效的点，所以有效大小是n
func NewStronglyConnectedComponents(edges [][]int) *StronglyConnectedComponents {
    ans := &StronglyConnectedComponents{}
    ans.nexts = edges
    ans.init()
    ans.scc0()
    return ans
}

func (this *StronglyConnectedComponents) init() {
    this.n = len(this.nexts)
    this.stack = make([]int, this.n)
    this.stackSize = 0
    this.dfn = make([]int, this.n)
    this.low = make([]int, this.n)
    this.cnt = 0
    this.scc = make([]int, this.n)
    this.sccn = 0
    this.n--
}

func (this *StronglyConnectedComponents) scc0() {
    for i := 1; i <= this.n; i++ {
        if this.dfn[i] == 0 {
            this.tarjan(i)
        }
    }
}

func (this *StronglyConnectedComponents) tarjan(p int) {
    this.cnt++
    this.dfn[p] = this.cnt
    this.low[p] = this.cnt
    this.stack[this.stackSize] = p
    this.stackSize++
    for _, q := range this.nexts[p] {
        if this.dfn[q] == 0 {
            this.tarjan(q)
        }
        if this.scc[q] == 0 {
            if this.low[p] > this.low[q] {
                this.low[p] = this.low[q]
            }
        }
    }
    if this.low[p] == this.dfn[p] {
        this.sccn++
        top := 0
        for {
            this.stackSize--
            top = this.stack[this.stackSize]
            this.scc[top] = this.sccn
            if top == p {
                break
            }
        }
    }
}

func (this *StronglyConnectedComponents) getScc() []int {
    return this.scc
}

func (this *StronglyConnectedComponents) getSccn() int {
    return this.sccn
}

func (this *StronglyConnectedComponents) getShortGraph() [][]int {
    shortGraph := make([][]int, 0)
    for i := 0; i <= this.sccn; i++ {
        shortGraph = append(shortGraph, make([]int, 0))
    }
    for u := 1; u <= this.n; u++ {
        for _, v := range this.nexts[u] {
            if this.scc[u] != this.scc[v] {
                shortGraph[this.scc[u]] = append(shortGraph[this.scc[u]], this.scc[v])
            }
        }
    }
    return shortGraph
}

执行结果如下：

---

左神java代码