Submission #47961861

---

Source Code Expand

import scala.collection.mutable
import scala.reflect.ClassTag

inline def rep(n: Int, f: => Unit): Unit = { var c = 0; while (c < n) { f; c += 1 } }
inline def rep(n: Int, f: Int => Unit): Unit = { var c = 0; while (c < n) { f(c); c += 1 } }

final class InputReader() {
  import scala.util.Using

  private var i = 0
  private val lines = Using(io.Source.fromFile("/dev/stdin"))(_.getLines().toArray).get
  private var tokenizer: java.util.StringTokenizer = null

  private def next(): String = {
    while (tokenizer == null || !tokenizer.hasMoreTokens) {
      tokenizer = java.util.StringTokenizer(lines(i))
      lines(i) = null
      i += 1
    }
    tokenizer.nextToken()
  }

  inline def nextStr(): String = next()
  inline def nextInt(): Int = java.lang.Integer.parseInt(next()) // inlined `String.toInt()`
  inline def nextLong(): Long = java.lang.Long.parseLong(next()) // inlined `String.toLong()`
}

object Main {

  def main(_args: Array[String]): Unit = {
    val in = new InputReader()
    val out = new java.io.PrintWriter(System.out)

    val n = in.nextInt()
    val m = in.nextInt()
    val g = SccGraph(n)
    (0 until m).foreach(_ => {
      val a = in.nextInt()
      val b = in.nextInt()

      g.addEdge(a, b)
    })

    try {
      val ans = g.scc()

      out.println(ans.size)
      for (vs <- ans) {
        out.print(s"${vs.size} ")
        out.println(vs.mkString(" "))
      }
    } catch {
      case e: Throwable =>
        e.printStackTrace(out)
    } finally {
      out.flush()
    }
  }

}

package internal {
  private[internal] case class Edge(to: Int)

  private[internal] case class Csr[E] private (start: Array[Int], eList: Array[E])
  private[internal] object Csr {
    def apply[E: ClassTag](n: Int, edges: collection.Seq[(Int, E)]): Csr[E] = {
      val csr = Csr(new Array[Int](n+1), new Array[E](edges.size))
      for ((from, _) <- edges) {
        csr.start(from + 1) += 1
      }
      (1 to n).foreach(i => {
        csr.start(i) += csr.start(i - 1)
      })
      val counter = csr.start.clone()
      for ((from, edge) <- edges) {
        csr.eList(counter(from)) = edge
        counter(from) += 1
      }
      csr
    }
  }

  /**
   * Reference:
   * R. Tarjan,
   * Depth-First Search and Linear Graph Algorithms
   */
  case class SccGraph(private val n: Int) {
    private val edges: mutable.Buffer[(Int, Edge)] = mutable.ListBuffer.empty

    def numVertices: Int = n

    def addEdge(from: Int, to: Int): Unit = {
      edges += ((from, Edge(to)))
    }

    private var g: Csr[Edge] = null
    private var now_ord = 0
    private var group_num = 0
    private var visited: mutable.Stack[Int] = null
    private var ord: Array[Int] = null
    private var low: Array[Int] = null
    private var ids: Array[Int] = null

    private def dfs(v: Int): Unit = {
      low(v) = now_ord
      ord(v) = now_ord
      now_ord += 1
      visited.push(v)
      (g.start(v) until g.start(v + 1)).foreach(i => {
        val to = g.eList(i).to
        if (ord(to) == -1) {
          dfs(to)
          low(v) = low(v).min(low(to))
        } else {
          low(v) = low(v).min(ord(to))
        }
      })
      if (low(v) == ord(v)) {
        while {
          // do
          val u = visited.pop()
          ord(u) = n
          ids(u) = group_num

          // while
          u != v
        } do {}
        group_num += 1
      }
    }

    /**
     * @return pair of (# of scc, scc id)
     */
    def sccIds(): (Int, Array[Int]) = {
      g = Csr(n, edges)
      now_ord = 0
      group_num = 0
      visited = new mutable.Stack[Int](n)
      ord = Array.fill(n)(-1)
      low = new Array[Int](n)
      ids = new Array[Int](n)

      (0 until n).foreach(i => {
        if (ord(i) == -1) { dfs(i) }
      })
      (0 until n).foreach(i => {
        ids(i) = group_num - 1 - ids(i)
      })

      (group_num, ids)
    }

    def scc(): collection.Seq[collection.Seq[Int]] = {
      val (group_nums, ids) = sccIds()
      val counts = new Array[Int](group_nums)
      ids.foreach(x => { counts(x) += 1 })
      val groups = new mutable.ArrayBuffer[mutable.Buffer[Int]](n)
      (0 until group_nums).foreach(i => {
        groups += new mutable.ArrayBuffer[Int](counts(i))
      })
      (0 until n).foreach(i => {
        groups(ids(i)) += i
      })

      groups
    }
  }
}

case class SccGraph(private val internal: _root_.internal.SccGraph) {

  def addEdge(from: Int, to: Int): Unit = {
    val n = internal.numVertices
    assert(0 <= from && from < n)
    assert(0 <= to && to < n)
    internal.addEdge(from, to)
  }

  def scc(): collection.Seq[collection.Seq[Int]] = {
    internal.scc()
  }

}

object SccGraph {
  def apply(n: Int): SccGraph = {
    new SccGraph(internal.SccGraph(n))
  }
}

Submission Info

Compile Error

[info] welcome to sbt 1.9.2 (Private Build Java 20.0.1)
[info] loading settings for project main-build from plugins.sbt ...
[info] loading project definition from /judge/main/project
[info] loading settings for project main from build.sbt ...
[info] set current project to main (in build file:/judge/main/)
[info] Defining offline
[info] The new value will be used by updateConfiguration
[info] Reapplying settings...
[info] set current project to main (in build file:/judge/main/)
[info] compiling 1 Scala source to /judge/main/target/scala-3.3.0/classes ...
[info] done compiling
[info] Linking (2663 ms)
[info] Checking intermediate code (quick) (155 ms)
[info] Discovered 864 classes and 5168 methods
[info] Optimizing (release-fast mode) (6181 ms)
[info] Generating intermediate code (3325 ms)
[info] Produced 1 files
[info] Compiling to native code (16098 ms)
[info] Total (28645 ms)
[success] Total time: 41 s, completed Nov 26, 2023, 6:35:50 AM

Judge Result