2022-05-16：A -> B，表示A认为B是红人，A -> B -> C，表示A认为B是红人，B认为C是红人，规定“认为”

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
}