先修科目を守る学期計画

import sysfrom collections import deque  def first_open(t, kind):    """t학기부터 세어 그 과목이 열리는 가장 이른 학기"""    if (kind == 1 and t % 2 == 0) or (kind == 2 and t % 2 == 1):        return t + 1    return t  data = sys.stdin.buffer.read().split()n, m = int(data[0]), int(data[1])kind = [0] + [int(x) for x in data[2:2 + n]]  # 0: 모든 학기, 1: 홀수 학기, 2: 짝수 학기after = [[] for _ in range(n + 1)]  # after[a] = a를 들어야 들을 수 있는 과목들waiting = [0] * (n + 1)            # 아직 듣지 않은 선수 과목의 수for i in range(m):    a, b = int(data[2 + n + 2 * i]), int(data[3 + n + 2 * i])    after[a].append(b)    waiting[b] += 1 earliest = [1] * (n + 1)  # 선수 과목만 보면 들을 수 있는 가장 이른 학기term = [-1] * (n + 1)     # 끝까지 -1이면 고리 때문에 들을 수 없다q = deque(v for v in range(1, n + 1) if waiting[v] == 0)while q:    a = q.popleft()    term[a] = first_open(earliest[a], kind[a])  # 선수 과목을 다 들었으니 이제 학기가 정해진다    for b in after[a]:        # 선수 과목 가운데 가장 늦은 것의 다음 학기        earliest[b] = max(earliest[b], term[a] + 1)        waiting[b] -= 1        if waiting[b] == 0:            q.append(b) print(" ".join(map(str, term[1:])))print(max([0] + term[1:]))  # 들을 수 있는 과목이 없으면 0

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const kind = [0, ...data.slice(2, 2 + n)]; // 0: 모든 학기, 1: 홀수 학기, 2: 짝수 학기 // t학기부터 세어 그 과목이 열리는 가장 이른 학기function firstOpen(t, k) {  if ((k === 1 && t % 2 === 0) || (k === 2 && t % 2 === 1)) return t + 1;  return t;} const after = Array.from({ length: n + 1 }, () => []); // after[a] = a를 들어야 들을 수 있는 과목들const waiting = new Array(n + 1).fill(0); // 아직 듣지 않은 선수 과목의 수for (let i = 0; i < m; i++) {  const a = data[2 + n + 2 * i], b = data[3 + n + 2 * i];  after[a].push(b);  waiting[b]++;} const earliest = new Array(n + 1).fill(1); // 선수 과목만 보면 들을 수 있는 가장 이른 학기const term = new Array(n + 1).fill(-1); // 끝까지 -1이면 고리 때문에 들을 수 없다const queue = [];for (let v = 1; v <= n; v++) if (waiting[v] === 0) queue.push(v);// shift()는 매번 앞을 당겨 느리니 머리 번호 head로 꺼낸다for (let head = 0; head < queue.length; head++) {  const a = queue[head];  term[a] = firstOpen(earliest[a], kind[a]); // 선수 과목을 다 들었으니 이제 학기가 정해진다  for (const b of after[a]) {    earliest[b] = Math.max(earliest[b], term[a] + 1); // 가장 늦은 선수 과목의 다음 학기    if (--waiting[b] === 0) queue.push(b);  }} const terms = term.slice(1);console.log(terms.join(" "));console.log(terms.reduce((x, y) => Math.max(x, y), 0));

import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0], m = data[1];const kind: number[] = [0, ...data.slice(2, 2 + n)]; // 0: 모든 학기, 1: 홀수 학기, 2: 짝수 학기 // t학기부터 세어 그 과목이 열리는 가장 이른 학기function firstOpen(t: number, k: number): number {  if ((k === 1 && t % 2 === 0) || (k === 2 && t % 2 === 1)) return t + 1;  return t;} const after: number[][] = Array.from({ length: n + 1 }, () => []); // after[a] = a를 들어야 들을 수 있는 과목들const waiting: number[] = new Array<number>(n + 1).fill(0); // 아직 듣지 않은 선수 과목의 수for (let i = 0; i < m; i++) {  const a = data[2 + n + 2 * i], b = data[3 + n + 2 * i];  after[a].push(b);  waiting[b]++;} const earliest: number[] = new Array<number>(n + 1).fill(1); // 선수 과목만 보면 들을 수 있는 가장 이른 학기const term: number[] = new Array<number>(n + 1).fill(-1); // 끝까지 -1이면 고리 때문에 들을 수 없다const queue: number[] = [];for (let v = 1; v <= n; v++) if (waiting[v] === 0) queue.push(v);for (let head = 0; head < queue.length; head++) {  const a = queue[head];  term[a] = firstOpen(earliest[a], kind[a]); // 선수 과목을 다 들었으니 이제 학기가 정해진다  for (const b of after[a]) {    earliest[b] = Math.max(earliest[b], term[a] + 1); // 가장 늦은 선수 과목의 다음 학기    if (--waiting[b] === 0) queue.push(b);  }} const terms = term.slice(1);console.log(terms.join(" "));console.log(terms.reduce((x, y) => Math.max(x, y), 0));

import java.io.*;import java.util.*; public class Main {    // t학기부터 세어 그 과목이 열리는 가장 이른 학기(kind 0: 모든 학기, 1: 홀수 학기, 2: 짝수 학기)    static int firstOpen(int t, int kind) {        if ((kind == 1 && t % 2 == 0) || (kind == 2 && t % 2 == 1)) return t + 1;        return t;    }     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;        st.nextToken();        int m = (int) st.nval;        int[] kind = new int[n + 1];        for (int v = 1; v <= n; v++) {            st.nextToken();            kind[v] = (int) st.nval;        }        List<List<Integer>> after = new ArrayList<>(); // after.get(a) = a를 들어야 들을 수 있는 과목들        for (int v = 0; v <= n; v++) after.add(new ArrayList<>());        int[] waiting = new int[n + 1]; // 아직 듣지 않은 선수 과목의 수        for (int i = 0; i < m; i++) {            st.nextToken();            int a = (int) st.nval;            st.nextToken();            int b = (int) st.nval;            after.get(a).add(b);            waiting[b]++;        }         int[] earliest = new int[n + 1]; // 선수 과목만 보면 들을 수 있는 가장 이른 학기        Arrays.fill(earliest, 1);        int[] term = new int[n + 1];        Arrays.fill(term, -1); // 끝까지 -1이면 고리 때문에 들을 수 없다        ArrayDeque<Integer> q = new ArrayDeque<>();        for (int v = 1; v <= n; v++) {            if (waiting[v] == 0) q.add(v);        }        while (!q.isEmpty()) {            int a = q.poll();            term[a] = firstOpen(earliest[a], kind[a]); // 선수 과목을 다 들었으니 이제 학기가 정해진다            for (int b : after.get(a)) {                earliest[b] = Math.max(earliest[b], term[a] + 1); // 가장 늦은 선수 과목의 다음 학기                if (--waiting[b] == 0) q.add(b);            }        }         StringBuilder sb = new StringBuilder();        int most = 0;        for (int v = 1; v <= n; v++) {            if (v > 1) sb.append(' ');            sb.append(term[v]);            most = Math.max(most, term[v]);        }        sb.append('\n').append(most).append('\n');        System.out.print(sb);    }}

using System;using System.Collections.Generic;using System.Text; class Program{    // t학기부터 세어 그 과목이 열리는 가장 이른 학기(kind 0: 모든 학기, 1: 홀수 학기, 2: 짝수 학기)    static int FirstOpen(int t, int kind)    {        if ((kind == 1 && t % 2 == 0) || (kind == 2 && t % 2 == 1)) return t + 1;        return t;    }     static void Main()    {        var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries);        int n = int.Parse(data[0]), m = int.Parse(data[1]);        var kind = new int[n + 1];        for (int v = 1; v <= n; v++) kind[v] = int.Parse(data[1 + v]);        var after = new List<int>[n + 1]; // after[a] = a를 들어야 들을 수 있는 과목들        for (int v = 0; v <= n; v++) after[v] = new List<int>();        var waiting = new int[n + 1]; // 아직 듣지 않은 선수 과목의 수        for (int i = 0; i < m; i++)        {            int a = int.Parse(data[2 + n + 2 * i]), b = int.Parse(data[3 + n + 2 * i]);            after[a].Add(b);            waiting[b]++;        }         var earliest = new int[n + 1]; // 선수 과목만 보면 들을 수 있는 가장 이른 학기        Array.Fill(earliest, 1);        var term = new int[n + 1];        Array.Fill(term, -1); // 끝까지 -1이면 고리 때문에 들을 수 없다        var q = new Queue<int>();        for (int v = 1; v <= n; v++)        {            if (waiting[v] == 0) q.Enqueue(v);        }        while (q.Count > 0)        {            int a = q.Dequeue();            term[a] = FirstOpen(earliest[a], kind[a]); // 선수 과목을 다 들었으니 이제 학기가 정해진다            foreach (int b in after[a])            {                earliest[b] = Math.Max(earliest[b], term[a] + 1); // 가장 늦은 선수 과목의 다음 학기                if (--waiting[b] == 0) q.Enqueue(b);            }        }         var sb = new StringBuilder();        int most = 0;        for (int v = 1; v <= n; v++)        {            if (v > 1) sb.Append(' ');            sb.Append(term[v]);            most = Math.Max(most, term[v]);        }        sb.Append('\n').Append(most).Append('\n');        Console.Write(sb);    }}

#include <algorithm>#include <iostream>#include <queue>#include <vector> // t학기부터 세어 그 과목이 열리는 가장 이른 학기(kind 0: 모든 학기, 1: 홀수 학기, 2: 짝수 학기)int firstOpen(int t, int kind) {    if ((kind == 1 && t % 2 == 0) || (kind == 2 && t % 2 == 1)) return t + 1;    return t;} int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int n, m;    std::cin >> n >> m;    std::vector<int> kind(n + 1);    for (int v = 1; v <= n; v++) std::cin >> kind[v];    std::vector<std::vector<int>> after(n + 1); // after[a] = a를 들어야 들을 수 있는 과목들    std::vector<int> waiting(n + 1, 0);          // 아직 듣지 않은 선수 과목의 수    for (int i = 0; i < m; i++) {        int a, b;        std::cin >> a >> b;        after[a].push_back(b);        waiting[b]++;    }     std::vector<int> earliest(n + 1, 1); // 선수 과목만 보면 들을 수 있는 가장 이른 학기    std::vector<int> term(n + 1, -1);    // 끝까지 -1이면 고리 때문에 들을 수 없다    std::queue<int> q;    for (int v = 1; v <= n; v++) {        if (waiting[v] == 0) q.push(v);    }    while (!q.empty()) {        int a = q.front();        q.pop();        term[a] = firstOpen(earliest[a], kind[a]); // 선수 과목을 다 들었으니 이제 학기가 정해진다        for (int b : after[a]) {            earliest[b] = std::max(earliest[b], term[a] + 1); // 가장 늦은 선수 과목의 다음 학기            if (--waiting[b] == 0) q.push(b);        }    }     int most = 0;    for (int v = 1; v <= n; v++) {        std::cout << (v > 1 ? " " : "") << term[v];        most = std::max(most, term[v]);    }    std::cout << "\n" << most << "\n";}

#include <stdio.h>#include <stdlib.h> // t학기부터 세어 그 과목이 열리는 가장 이른 학기(kind 0: 모든 학기, 1: 홀수 학기, 2: 짝수 학기)int first_open(int t, int kind) {    if ((kind == 1 && t % 2 == 0) || (kind == 2 && t % 2 == 1)) return t + 1;    return t;} int main(void) {    int n, m;    if (scanf("%d %d", &n, &m) != 2) return 0;    int *kind = malloc((n + 1) * sizeof(int));    for (int v = 1; v <= n; v++) scanf("%d", &kind[v]);    // 이음 목록을 배열 셋으로: head[a]에서 시작해 next[e]로 따라가며 to[e]를 본다    int *head = malloc((n + 1) * sizeof(int));    int *next = malloc((m + 1) * sizeof(int));    int *to = malloc((m + 1) * sizeof(int));    int *waiting = calloc(n + 1, sizeof(int)); // 아직 듣지 않은 선수 과목의 수    int *earliest = malloc((n + 1) * sizeof(int)); // 선수 과목만 보면 들을 수 있는 가장 이른 학기    int *term = malloc((n + 1) * sizeof(int));    int *queue = malloc((n + 1) * sizeof(int));    for (int v = 0; v <= n; v++) {        head[v] = -1;        earliest[v] = 1;        term[v] = -1; // 끝까지 -1이면 고리 때문에 들을 수 없다    }    for (int e = 0; e < m; e++) {        int a, b;        scanf("%d %d", &a, &b);        to[e] = b;        next[e] = head[a];        head[a] = e;        waiting[b]++;    }     int qh = 0, qt = 0;    for (int v = 1; v <= n; v++) {        if (waiting[v] == 0) queue[qt++] = v;    }    while (qh < qt) {        int a = queue[qh++];        term[a] = first_open(earliest[a], kind[a]); // 선수 과목을 다 들었으니 이제 학기가 정해진다        for (int e = head[a]; e != -1; e = next[e]) {            int b = to[e];            if (term[a] + 1 > earliest[b]) earliest[b] = term[a] + 1; // 가장 늦은 선수 과목의 다음 학기            if (--waiting[b] == 0) queue[qt++] = b;        }    }     int most = 0;    for (int v = 1; v <= n; v++) {        printf(v > 1 ? " %d" : "%d", term[v]);        if (term[v] > most) most = term[v];    }    printf("\n%d\n", most);    free(kind); free(head); free(next); free(to); free(waiting); free(earliest); free(term); free(queue);    return 0;}

// t학기부터 세어 그 과목이 열리는 가장 이른 학기(종류 0: 모든 학기, 1: 홀수 학기, 2: 짝수 학기)열리는학기(t, 종류){    もし (종류 == 1 && t % 2 == 0 || 종류 == 2 && t % 2 == 1)    {        返す t + 1;    }    返す t;} 첫줄 = コンソール.数読み();n = 첫줄[0];m = 첫줄[1];// 목록은 10,000칸까지라 과목 번호에서 1을 빼 0번부터 둔다kind = コンソール.数読み(); after = []; // after[a] = a를 들어야 들을 수 있는 과목들繰り返す (v = 0; v < n; v++){    after.追加([]);}waiting = 新リスト(n, 0); // 아직 듣지 않은 선수 과목의 수繰り返す (i = 0; i < m; i++){    쌍 = コンソール.数読み();    after[쌍[0] - 1].追加(쌍[1] - 1);    waiting[쌍[1] - 1] += 1;} earliest = 新リスト(n, 1); // 선수 과목만 보면 들을 수 있는 가장 이른 학기term = 新リスト(n, -1); // 끝까지 -1이면 고리 때문에 들을 수 없다queue = [];繰り返す (v = 0; v < n; v++){    もし (waiting[v] == 0)    {        queue.追加(v);    }}// 앞에서 꺼내는 대신 머리 번호 head를 옮긴다head = 0;間 (head < queue.個数){    a = queue[head];    head++;    term[a] = 열리는학기(earliest[a], kind[a]); // 선수 과목을 다 들었으니 이제 학기가 정해진다    それぞれ (b の中 after[a])    {        earliest[b] = 数学.大きい方(earliest[b], term[a] + 1); // 가장 늦은 선수 과목의 다음 학기        waiting[b] -= 1;        もし (waiting[b] == 0)        {            queue.追加(b);        }    }} most = 0;それぞれ (t の中 term){    most = 数学.大きい方(most, t);}コンソール.書く(term);コンソール.書く(most);