2022-05-16：A -＞ B，表示A认为B是红人， A -＞ B -＞ C，表示A认为B是红人，B认为C是红人，规定“认为”关系有传递性，所以A也认为C是红人， 给定一张有向图，方式是给定M个有

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代码

2022-05-16：A -＞ B，表示A认为B是红人， A -＞ B -＞ C，表示A认为B是红人，B认为C是红人，规定“认为”关系有传递性，所以A也认为C是红人， 给定一张有向图，方式是给定M个有的相关教程结束。