AtCoder Beginner Contest 454 C

https://atcoder.jp/contests/abc454/tasks/abc454_c

有向グラフを1から辿るだけですが、Rでグラフをふつうに作る全然時間が足りません。そこでノードの隣のノードの配列をリストにします。こうすると時間内に収まります。

v <- scan("stdin", integer())

N <- v[1]
M <- v[2]
edges <- v[3:(M*2+2)]

# グラフを作る
# [隣のノード、次の隣のノードのindex. ...]
graph <- rep(-1, M*2+N*2)
# 今の隣のノードの末尾のindex
ps <- 1:N*2-1
p <- N*2+1
for(i in 1:M) {
    A <- edges[i*2-1]
    B <- edges[i*2]
    q <- ps[A]
    graph[q] <- B
    graph[q+1] <- p
    ps[A] <- p
    p <- p + 2
}

stack <- rep(-1, N)
stack[1] <- 1
pos <- 1
visited <- rep(FALSE, N)
visited[1] = TRUE

while(pos > 0) {
    v0 <- stack[pos]    # 今調べるノード
    pos <- pos - 1
    index <- v0*2-1
    while(TRUE) {
        v1 <- graph[index]  # v0の隣のノード
        if(v1 == -1) {
            break
        }
        index = graph[index+1]
        if(visited[v1]) {
            next
        }
        visited[v1] = TRUE
        pos <- pos + 1
        stack[pos] <- v1
    }
}

num <- sum(as.integer(visited))
cat(num, "\n")