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 main

import "fmt"

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

func 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才是有效的点，所以有效大小是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代码