접힌 댓글 타래의 줄 번호

import sys data = sys.stdin.read().split()n = int(data[0])parent = [0] + [int(x) for x in data[1:1 + n]]          # parent[i] = i가 답한 댓글(0이면 글에 바로 단 댓글)folded = [0] + [int(x) for x in data[1 + n:1 + 2 * n]]  # folded[i] = 1이면 접힌 댓글 # replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다# replies[0]은 글에 바로 단 댓글들이다replies = [[] for _ in range(n + 1)]for i in range(1, n + 1):    replies[parent[i]].append(i) # 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다# 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다line = [0] * (n + 1)shown = 0stack = replies[0][::-1]while stack:    v = stack.pop()    shown += 1    line[v] = shown    if not folded[v]:  # 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다        stack.extend(reversed(replies[v])) print(shown)print(" ".join(map(str, line[1:])))

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];// replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다// replies[0]은 글에 바로 단 댓글들이다const replies = Array.from({ length: n + 1 }, () => []);for (let i = 1; i <= n; i++) replies[data[i]].push(i);const folded = (v) => data[n + v] === 1; // 접힌 댓글인가 // 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다// 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다const line = new Array(n + 1).fill(0);let shown = 0;const stack = [...replies[0]].reverse();while (stack.length > 0) {  const v = stack.pop();  line[v] = ++shown;  if (folded(v)) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다  for (let k = replies[v].length - 1; k >= 0; k--) stack.push(replies[v][k]);} console.log(shown);console.log(line.slice(1).join(" "));

import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];// replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다// replies[0]은 글에 바로 단 댓글들이다const replies: number[][] = Array.from({ length: n + 1 }, (): number[] => []);for (let i = 1; i <= n; i++) replies[data[i]].push(i);const folded = (v: number): boolean => data[n + v] === 1; // 접힌 댓글인가 // 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다// 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다const line: number[] = new Array<number>(n + 1).fill(0);let shown = 0;const stack: number[] = [...replies[0]].reverse();while (stack.length > 0) {  const v = stack.pop() as number;  line[v] = ++shown;  if (folded(v)) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다  for (let k = replies[v].length - 1; k >= 0; k--) stack.push(replies[v][k]);} console.log(shown);console.log(line.slice(1).join(" "));

import java.io.*;import java.util.*; public class Main {    public static void main(String[] args) throws IOException {        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));        st.nextToken();        int n = (int) st.nval;        // replies.get(v) = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다        // replies.get(0)은 글에 바로 단 댓글들이다        List<List<Integer>> replies = new ArrayList<>();        for (int v = 0; v <= n; v++) replies.add(new ArrayList<>());        for (int i = 1; i <= n; i++) {            st.nextToken();            replies.get((int) st.nval).add(i);        }        boolean[] folded = new boolean[n + 1];        for (int i = 1; i <= n; i++) {            st.nextToken();            folded[i] = st.nval == 1;        }         // 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다        // 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다        int[] line = new int[n + 1];        int shown = 0;        ArrayDeque<Integer> stack = new ArrayDeque<>();        stack.push(0); // 0번은 글 자체: 줄을 차지하지 않고 접히지도 않는다        while (!stack.isEmpty()) {            int v = stack.pop();            if (v != 0) line[v] = ++shown;            if (folded[v]) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다            List<Integer> r = replies.get(v);            for (int k = r.size() - 1; k >= 0; k--) stack.push(r.get(k));        }         StringBuilder sb = new StringBuilder();        sb.append(shown).append('\n');        for (int i = 1; i <= n; i++) sb.append(line[i]).append(i < n ? ' ' : '\n');        System.out.print(sb);    }}

using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries);        int n = int.Parse(data[0]);        // replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다        // replies[0]은 글에 바로 단 댓글들이다        var replies = new List<int>[n + 1];        for (int v = 0; v <= n; v++) replies[v] = new List<int>();        for (int i = 1; i <= n; i++) replies[int.Parse(data[i])].Add(i);        var folded = new bool[n + 1];        for (int i = 1; i <= n; i++) folded[i] = data[n + i] == "1";         // 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다        // 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다        var line = new int[n + 1];        int shown = 0;        var stack = new Stack<int>();        stack.Push(0); // 0번은 글 자체: 줄을 차지하지 않고 접히지도 않는다        while (stack.Count > 0)        {            int v = stack.Pop();            if (v != 0) line[v] = ++shown;            if (folded[v]) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다            for (int k = replies[v].Count - 1; k >= 0; k--) stack.Push(replies[v][k]);        }         var sb = new StringBuilder();        sb.Append(shown).Append('\n');        for (int i = 1; i <= n; i++) sb.Append(line[i]).Append(i < n ? ' ' : '\n');        Console.Write(sb);    }}

#include <iostream>#include <stack>#include <vector>using namespace std; int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n;    cin >> n;    // replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다    // replies[0]은 글에 바로 단 댓글들이다    vector<vector<int>> replies(n + 1);    for (int i = 1; i <= n; i++) {        int p;        cin >> p;        replies[p].push_back(i);    }    vector<int> folded(n + 1, 0);    for (int i = 1; i <= n; i++) cin >> folded[i];     // 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다    // 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다    vector<int> line(n + 1, 0);    int shown = 0;    stack<int> st;    st.push(0); // 0번은 글 자체: 줄을 차지하지 않고 접히지도 않는다    while (!st.empty()) {        int v = st.top();        st.pop();        if (v != 0) line[v] = ++shown;        if (folded[v]) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다        for (auto it = replies[v].rbegin(); it != replies[v].rend(); ++it) st.push(*it);    }     cout << shown << '\n';    for (int i = 1; i <= n; i++) cout << line[i] << (i < n ? ' ' : '\n');    return 0;}

#include <stdio.h>#include <stdlib.h> int main(void) {    int n;    if (scanf("%d", &n) != 1) return 0;    // 답글 목록을 배열 둘로: first[v]에서 시작해 next[i]로 따라간다(v = 0은 글 자체)    // 새 답글을 목록의 맨 앞에 끼우므로, 따라가면 번호가 큰 답글부터 나온다    int *first = calloc(n + 1, sizeof(int));    int *next = calloc(n + 1, sizeof(int));    int *folded = calloc(n + 1, sizeof(int));    for (int i = 1; i <= n; i++) {        int p;        scanf("%d", &p);        next[i] = first[p];        first[p] = i;    }    for (int i = 1; i <= n; i++) scanf("%d", &folded[i]);     // 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다    // 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다    int *line = calloc(n + 1, sizeof(int));    int *stack = malloc((n + 1) * sizeof(int)); // 댓글마다 한 번만 들어간다    int top = 0, shown = 0;    stack[top++] = 0; // 0번은 글 자체: 줄을 차지하지 않고 접히지도 않는다    while (top > 0) {        int v = stack[--top];        if (v != 0) line[v] = ++shown;        if (folded[v]) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다        for (int r = first[v]; r != 0; r = next[r]) stack[top++] = r;    }     printf("%d\n", shown);    for (int i = 1; i <= n; i++) printf(i > 1 ? " %d" : "%d", line[i]);    printf("\n");    free(first); free(next); free(folded); free(line); free(stack);    return 0;}

n = 콘솔.수들읽기()[0];parent = 콘솔.수들읽기(); // parent[i - 1] = i번 댓글이 답한 댓글(0이면 글에 바로 단 댓글)folded = 콘솔.수들읽기(); // folded[i - 1] = 1이면 접힌 댓글 // 목록은 10,000칸까지라 댓글 번호에서 1을 빼 0번부터 둔다// replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 차례로 넣으면 번호 순이 된다replies = [];반복 (v = 0; v < n; v++){    replies.넣기([]);}tops = []; // 글에 바로 단 댓글들반복 (i = 0; i < n; i++){    만약 (parent[i] == 0)    {        tops.넣기(i);    }    아니면    {        replies[parent[i] - 1].넣기(i);    }} // 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다// 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다line = 새목록(n, 0);shown = 0;stack = [];반복 (k = tops.개수 - 1; k >= 0; k--){    stack.넣기(tops[k]);}동안 (stack.개수 > 0){    v = stack[stack.개수 - 1];    stack.자리빼기(stack.개수 - 1);    shown += 1;    line[v] = shown;    // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다    만약 (folded[v] == 0)    {        반복 (k = replies[v].개수 - 1; k >= 0; k--)        {            stack.넣기(replies[v][k]);        }    }} 콘솔.쓰기(shown);콘솔.쓰기(line);