2022-05-15：N个学校之间有单向的 络，每个学校得到一套软件后

2022-05-15：N个学校之间有单向的 络，每个学校得到一套软件后，可以通过单向 络向周边的学校传输。

问题1：初始至少需要向多少个学校发放软件，使得 络内所有的学校最终都能得到软件；

问题2：至少需要添加几条传输线路(边)，使任意向一个学校发放软件后。

经过若干次传送， 络内所有的学校最终都能得到软件。

2 <= N <= 1000。

从题意中抽象出的算法模型, 给定一个有向图，求：

1) 至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点；

2) 至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点。

测试链接 : http://poj.org/problem?id=1236，

注册一下 -> 页面上点击”submit” -> 语言选择java，

然后把如下代码粘贴进去, 把主类名改成”Main”, 可以直接通过。

强连通分量练习题目。

答案2022-05-15：

tarjan算法。

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

package mainimport "fmt"var sc = []int{5, 2, 4, 3, 0, 4, 5, 0, 0, 0, 1, 0}var ii = 0func next() int {	ii++	return sc[ii-1]}func hasNext() bool {	return ii < len(sc)}func main() {	for hasNext() {		n := next()		edges := make([][]int, 0)		for i := 0; i <= n; i++ {			edges = append(edges, make([]int, 0))		}		for from := 1; from <= n; from++ {			to := 0			to = next()			for to != 0 {				edges[from] = append(edges[from], to)				to = next()			}		}		scc := NewStronglyConnectedComponents(edges)		sccn := scc.getSccn()		in := make([]int, sccn+1)		out := make([]int, sccn+1)		dag := scc.getShortGraph()		for i := 1; i <= sccn; i++ {			for _, j := range dag[i] {				out[i]++				in[j]++			}		}		zeroIn := 0		zeroOut := 0		for i := 1; i <= sccn; i++ {			if in[i] == 0 {				zeroIn++			}			if out[i] == 0 {				zeroOut++			}		}		fmt.Println(zeroIn)		fmt.Println(sccn == 1, 0, getMax(zeroIn, zeroOut))	}}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才是有效的点，所以有效大小是nfunc 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代码](
https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_03_1_week/Code02_NetworkOfSchools.java)