前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-05-15:N个学校之间有单向的网络,每个学校得到一套软件后,可以通过单向网络向周边的学校传输。

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

作者头像
福大大架构师每日一题
发布2022-06-04 10:58:47
1960
发布2022-06-04 10:58:47
举报

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编写。代码如下:

代码语言:javascript
复制
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代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_03_1_week/Code02_NetworkOfSchools.java

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-05-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档