安排任务顺序

import heapqimport sys data = sys.stdin.read().split()n, m = int(data[0]), int(data[1]) after = [[] for _ in range(n + 1)]  # after[a] = a를 끝내야 할 수 있는 일들waiting = [0] * (n + 1)             # waiting[b] = b보다 먼저 끝내야 하는데 아직 안 끝난 일의 수for i in range(m):    a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])    after[a].append(b)    waiting[b] += 1 # 지금 할 수 있는 일들을 최소 힙에 두고, 늘 가장 작은 번호를 꺼낸다ready = [t for t in range(1, n + 1) if waiting[t] == 0]heapq.heapify(ready)order = []while ready:    t = heapq.heappop(ready)    order.append(t)    for nxt in after[t]:        waiting[nxt] -= 1        if waiting[nxt] == 0:            heapq.heappush(ready, nxt) # 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다print(" ".join(map(str, order)) if len(order) == n else -1)

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data; // 최소 힙: heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2class MinHeap {  constructor() {    this.items = [];  }  get size() {    return this.items.length;  }  push(x) {    const a = this.items;    a.push(x);    let i = a.length - 1;    while (i > 0) {      const parent = (i - 1) >> 1;      if (a[parent] <= a[i]) break;      [a[parent], a[i]] = [a[i], a[parent]];      i = parent;    }  }  pop() {    const a = this.items;    const top = a[0];    const last = a.pop();    if (a.length > 0) {      a[0] = last;      let i = 0;      for (;;) {        const l = 2 * i + 1, r = l + 1;        let small = i;        if (l < a.length && a[l] < a[small]) small = l;        if (r < a.length && a[r] < a[small]) small = r;        if (small === i) break;        [a[small], a[i]] = [a[i], a[small]];        i = small;      }    }    return top;  }} 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 + 2 * i], b = data[3 + 2 * i];  after[a].push(b);  waiting[b]++;} const ready = new MinHeap(); // 지금 할 수 있는 일들. 늘 가장 작은 번호를 꺼낸다for (let t = 1; t <= n; t++) if (waiting[t] === 0) ready.push(t);const order = [];while (ready.size > 0) {  const t = ready.pop();  order.push(t);  for (const next of after[t]) {    if (--waiting[next] === 0) ready.push(next);  }}// 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다console.log(order.length === n ? order.join(" ") : "-1");

import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data; // 최소 힙: heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2class MinHeap {  private items: number[] = [];   get size(): number {    return this.items.length;  }   push(x: number): void {    const a = this.items;    a.push(x);    let i = a.length - 1;    while (i > 0) {      const parent = (i - 1) >> 1;      if (a[parent] <= a[i]) break;      [a[parent], a[i]] = [a[i], a[parent]];      i = parent;    }  }   pop(): number {    const a = this.items;    const top = a[0];    const last = a.pop()!; // size > 0일 때만 부른다    if (a.length > 0) {      a[0] = last;      let i = 0;      for (;;) {        const l = 2 * i + 1, r = l + 1;        let small = i;        if (l < a.length && a[l] < a[small]) small = l;        if (r < a.length && a[r] < a[small]) small = r;        if (small === i) break;        [a[small], a[i]] = [a[i], a[small]];        i = small;      }    }    return top;  }} const after: number[][] = Array.from({ length: n + 1 }, (): number[] => []); // after[a] = a를 끝내야 할 수 있는 일들const waiting: number[] = new Array<number>(n + 1).fill(0); // 먼저 끝내야 하는데 아직 안 끝난 일의 수for (let i = 0; i < m; i++) {  const a = data[2 + 2 * i], b = data[3 + 2 * i];  after[a].push(b);  waiting[b]++;} const ready = new MinHeap(); // 지금 할 수 있는 일들. 늘 가장 작은 번호를 꺼낸다for (let t = 1; t <= n; t++) if (waiting[t] === 0) ready.push(t);const order: number[] = [];while (ready.size > 0) {  const t = ready.pop();  order.push(t);  for (const next of after[t]) {    if (--waiting[next] === 0) ready.push(next);  }}// 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다console.log(order.length === n ? order.join(" ") : "-1");

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.PriorityQueue;import java.util.StringTokenizer; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(in.readLine());        int n = Integer.parseInt(st.nextToken());        int m = Integer.parseInt(st.nextToken());         List<List<Integer>> after = new ArrayList<>(); // after.get(a) = a를 끝내야 할 수 있는 일들        for (int t = 0; t <= n; t++) after.add(new ArrayList<>());        int[] waiting = new int[n + 1]; // 먼저 끝내야 하는데 아직 안 끝난 일의 수        for (int i = 0; i < m; i++) {            st = new StringTokenizer(in.readLine());            int a = Integer.parseInt(st.nextToken());            int b = Integer.parseInt(st.nextToken());            after.get(a).add(b);            waiting[b]++;        }         // PriorityQueue는 기본이 최소 힙: poll()이 늘 가장 작은 번호를 꺼낸다        PriorityQueue<Integer> ready = new PriorityQueue<>();        for (int t = 1; t <= n; t++) if (waiting[t] == 0) ready.add(t);        StringBuilder out = new StringBuilder();        int done = 0;        while (!ready.isEmpty()) {            int t = ready.poll();            if (done++ > 0) out.append(' ');            out.append(t);            for (int next : after.get(t)) {                if (--waiting[next] == 0) ready.add(next);            }        }        // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다        System.out.println(done == n ? out.toString() : "-1");    }}

using System;using System.Collections.Generic; class Program{    static void Main()    {        string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        int n = int.Parse(first[0]);        int m = int.Parse(first[1]);         var after = new List<int>[n + 1]; // after[a] = a를 끝내야 할 수 있는 일들        for (int t = 0; t <= n; t++) after[t] = new List<int>();        var waiting = new int[n + 1]; // 먼저 끝내야 하는데 아직 안 끝난 일의 수        for (int i = 0; i < m; i++)        {            string[] pair = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            int a = int.Parse(pair[0]);            int b = int.Parse(pair[1]);            after[a].Add(b);            waiting[b]++;        }         // PriorityQueue<값, 우선순위>: 우선순위가 작은 것부터 나온다. 번호를 우선순위로도 쓴다        var ready = new PriorityQueue<int, int>();        for (int t = 1; t <= n; t++) if (waiting[t] == 0) ready.Enqueue(t, t);        var order = new List<int>();        while (ready.Count > 0)        {            int t = ready.Dequeue();            order.Add(t);            foreach (int next in after[t])            {                if (--waiting[next] == 0) ready.Enqueue(next, next);            }        }        // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다        Console.WriteLine(order.Count == n ? string.Join(" ", order) : "-1");    }}

#include <functional>#include <iostream>#include <queue>#include <vector> int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int n, m;    std::cin >> n >> m;     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::priority_queue는 기본이 최대 힙이라 std::greater를 줘서 가장 작은 것이 위로 오게 한다    std::priority_queue<int, std::vector<int>, std::greater<int>> ready;    for (int t = 1; t <= n; t++)        if (waiting[t] == 0) ready.push(t);    std::vector<int> order;    while (!ready.empty()) {        int t = ready.top();        ready.pop();        order.push_back(t);        for (int next : after[t])            if (--waiting[next] == 0) ready.push(next);    }     // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다    if (static_cast<int>(order.size()) < n) {        std::cout << -1 << "\n";    } else {        for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << order[i];        std::cout << "\n";    }}

#include <stdio.h> #define MAXN 10001#define MAXM 10000 /* 인접 목록을 배열로: head[a]는 a 뒤에 할 수 있는 첫 일 칸, next[e]는 다음 칸(-1이면 끝) */static int head[MAXN], next[MAXM], to[MAXM];static int waiting[MAXN]; /* 먼저 끝내야 하는데 아직 안 끝난 일의 수 */static int heap[MAXN], heap_size = 0; /* 최소 힙: heap[0]이 가장 작다 */static int order[MAXN]; static void swap(int* x, int* y) {    int t = *x;    *x = *y;    *y = t;} static void heap_push(int x) {    int i = heap_size++;    heap[i] = x;    while (i > 0 && heap[(i - 1) / 2] > heap[i]) {        swap(&heap[(i - 1) / 2], &heap[i]);        i = (i - 1) / 2;    }} static int heap_pop(void) {    int top = heap[0];    heap[0] = heap[--heap_size];    int i = 0;    for (;;) {        int l = 2 * i + 1, r = l + 1, small = i;        if (l < heap_size && heap[l] < heap[small]) small = l;        if (r < heap_size && heap[r] < heap[small]) small = r;        if (small == i) break;        swap(&heap[small], &heap[i]);        i = small;    }    return top;} int main(void) {    int n, m;    scanf("%d %d", &n, &m);    for (int t = 1; t <= n; t++) head[t] = -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]++;    }     for (int t = 1; t <= n; t++)        if (waiting[t] == 0) heap_push(t);    int done = 0;    while (heap_size > 0) {        int t = heap_pop(); /* 지금 할 수 있는 일 가운데 가장 작은 번호 */        order[done++] = t;        for (int e = head[t]; e != -1; e = next[e])            if (--waiting[to[e]] == 0) heap_push(to[e]);    }     /* 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다 */    if (done < n) {        puts("-1");    } else {        for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", order[i]);        putchar('\n');    }    return 0;}

// 최소 힙(목록 heap): heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){    heap.添加(x);    i = heap.数量 - 1;    当 (i > 0)    {        부모 = 数学.商(i - 1, 2);        如果 (heap[부모] <= heap[i])        {            跳出;        }        t = heap[부모];        heap[부모] = heap[i];        heap[i] = t;        i = 부모;    }} 힙꺼내기(heap){    top = heap[0];    heap[0] = heap[heap.数量 - 1];    heap.按位置移除(heap.数量 - 1);    i = 0;    当 (真)    {        l = 2 * i + 1;        r = l + 1;        small = i;        如果 (l < heap.数量 && heap[l] < heap[small])        {            small = l;        }        如果 (r < heap.数量 && heap[r] < heap[small])        {            small = r;        }        如果 (small == i)        {            跳出;        }        t = heap[small];        heap[small] = heap[i];        heap[i] = t;        i = small;    }    返回 top;} 첫줄 = 控制台.读数字();n = 첫줄[0];m = 첫줄[1]; // 목록은 10,000칸까지라 일 번호에서 1을 빼 0번부터 둔다after = []; // after[a] = a를 끝내야 할 수 있는 일들循环 (t = 0; t < n; t++){    after.添加([]);}waiting = 新列表(n, 0); // 먼저 끝내야 하는데 아직 안 끝난 일의 수循环 (i = 0; i < m; i++){    쌍 = 控制台.读数字();    after[쌍[0] - 1].添加(쌍[1] - 1);    waiting[쌍[1] - 1] += 1;} ready = []; // 지금 할 수 있는 일들(최소 힙). 늘 가장 작은 번호를 꺼낸다循环 (t = 0; t < n; t++){    如果 (waiting[t] == 0)    {        힙넣기(ready, t);    }}order = [];当 (ready.数量 > 0){    t = 힙꺼내기(ready);    order.添加(t + 1);    遍历 (next 在 after[t])    {        waiting[next] -= 1;        如果 (waiting[next] == 0)        {            힙넣기(ready, next);        }    }} // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다如果 (order.数量 == n){    控制台.输出(order);}否则{    控制台.输出(-1);}