2022-05-15：N个学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输。
问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件；
问题2：至少需要添加几条传输线路(边)，使任意向一个学校发放软件后。
经过若干次传送，网络内所有的学校最终都能得到软件。
2 <= N <= 1000。
从题意中抽象出的算法模型, 给定一个有向图，求：
- 至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点；
至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点。
测试链接 : 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代码
