幅優先探索とトポロジカルソート

from collections import deque n, m = map(int, input().split())adj = [[] for _ in range(n + 1)]  # adj[a] = a를 끝내야 시작할 수 있는 일들need = [0] * (n + 1)  # need[b] = b보다 먼저 해야 하는데 아직 안 끝난 일의 수for _ in range(m):    a, b = map(int, input().split())    adj[a].append(b)    need[b] += 1 # 너비 우선 탐색: 1번 일에서 화살표를 가장 적게 몇 번 따라가면 닿는지dist = [-1] * (n + 1)  # -1이면 아직 안 간 곳dist[1] = 0queue = deque([1])while queue:    v = queue.popleft()    for w in adj[v]:        if dist[w] == -1:            dist[w] = dist[v] + 1  # 큐에 넣을 때 바로 적어요            queue.append(w)print(*dist[1:]) # 위상 정렬: 먼저 할 일이 남지 않은 일부터 꺼내요order = []queue = deque(v for v in range(1, n + 1) if need[v] == 0)while queue:    v = queue.popleft()    order.append(v)    for w in adj[v]:        need[w] -= 1  # v가 끝났으니 w가 기다리는 일이 하나 줄어요        if need[w] == 0:            queue.append(w)print(*order)

const [[n, m], ...pairs] = require("fs").readFileSync(0, "utf8").trim().split("\n").map((l) => l.trim().split(/\s+/).map(Number));const adj = Array.from({ length: n + 1 }, () => []); // adj[a] = a를 끝내야 시작할 수 있는 일들const need = new Array(n + 1).fill(0); // need[b] = b보다 먼저 해야 하는데 아직 안 끝난 일의 수for (const [a, b] of pairs.slice(0, m)) {  adj[a].push(b);  need[b]++;} // 너비 우선 탐색: 1번 일에서 화살표를 가장 적게 몇 번 따라가면 닿는지const dist = new Array(n + 1).fill(-1); // -1이면 아직 안 간 곳dist[1] = 0;let queue = [1];let head = 0; // 큐의 맨 앞 자리. 꺼낼 때마다 한 칸씩 뒤로 가요while (head < queue.length) {  const v = queue[head++];  for (const w of adj[v]) {    if (dist[w] === -1) {      dist[w] = dist[v] + 1; // 큐에 넣을 때 바로 적어요      queue.push(w);    }  }}console.log(dist.slice(1).join(" ")); // 위상 정렬: 먼저 할 일이 남지 않은 일부터 꺼내요const order = [];queue = [];head = 0;for (let v = 1; v <= n; v++) {  if (need[v] === 0) queue.push(v);}while (head < queue.length) {  const v = queue[head++];  order.push(v);  for (const w of adj[v]) {    need[w]--; // v가 끝났으니 w가 기다리는 일이 하나 줄어요    if (need[w] === 0) queue.push(w);  }}console.log(order.join(" "));

import { readFileSync } from "node:fs";const [[n, m], ...pairs]: number[][] = readFileSync(0, "utf8").trim().split("\n").map((l) => l.trim().split(/\s+/).map(Number));const adj: number[][] = Array.from({ length: n + 1 }, () => []); // adj[a] = a를 끝내야 시작할 수 있는 일들const need: number[] = new Array<number>(n + 1).fill(0); // need[b] = b보다 먼저 해야 하는데 아직 안 끝난 일의 수for (const [a, b] of pairs.slice(0, m)) {  adj[a].push(b);  need[b]++;} // 너비 우선 탐색: 1번 일에서 화살표를 가장 적게 몇 번 따라가면 닿는지const dist: number[] = new Array<number>(n + 1).fill(-1); // -1이면 아직 안 간 곳dist[1] = 0;let queue: number[] = [1];let head: number = 0; // 큐의 맨 앞 자리. 꺼낼 때마다 한 칸씩 뒤로 가요while (head < queue.length) {  const v = queue[head++];  for (const w of adj[v]) {    if (dist[w] === -1) {      dist[w] = dist[v] + 1; // 큐에 넣을 때 바로 적어요      queue.push(w);    }  }}console.log(dist.slice(1).join(" ")); // 위상 정렬: 먼저 할 일이 남지 않은 일부터 꺼내요const order: number[] = [];queue = [];head = 0;for (let v = 1; v <= n; v++) {  if (need[v] === 0) queue.push(v);}while (head < queue.length) {  const v = queue[head++];  order.push(v);  for (const w of adj[v]) {    need[w]--; // v가 끝났으니 w가 기다리는 일이 하나 줄어요    if (need[w] === 0) queue.push(w);  }}console.log(order.join(" "));

import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Scanner; public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt(), m = sc.nextInt();        ArrayList<ArrayList<Integer>> adj = new ArrayList<>(); // adj.get(a) = a를 끝내야 시작할 수 있는 일들        for (int v = 0; v <= n; v++) adj.add(new ArrayList<>());        int[] need = new int[n + 1]; // need[b] = b보다 먼저 해야 하는데 아직 안 끝난 일의 수        for (int i = 0; i < m; i++) {            int a = sc.nextInt(), b = sc.nextInt();            adj.get(a).add(b);            need[b]++;        }         // 너비 우선 탐색: 1번 일에서 화살표를 가장 적게 몇 번 따라가면 닿는지        int[] dist = new int[n + 1];        Arrays.fill(dist, -1); // -1이면 아직 안 간 곳        dist[1] = 0;        ArrayDeque<Integer> queue = new ArrayDeque<>();        queue.add(1);        while (!queue.isEmpty()) {            int v = queue.poll();            for (int w : adj.get(v)) {                if (dist[w] == -1) {                    dist[w] = dist[v] + 1; // 큐에 넣을 때 바로 적어요                    queue.add(w);                }            }        }        StringBuilder sb = new StringBuilder();        for (int v = 1; v <= n; v++) sb.append(v > 1 ? " " : "").append(dist[v]);        System.out.println(sb);         // 위상 정렬: 먼저 할 일이 남지 않은 일부터 꺼내요        StringBuilder order = new StringBuilder();        for (int v = 1; v <= n; v++) {            if (need[v] == 0) queue.add(v);        }        while (!queue.isEmpty()) {            int v = queue.poll();            order.append(order.length() > 0 ? " " : "").append(v);            for (int w : adj.get(v)) {                need[w]--; // v가 끝났으니 w가 기다리는 일이 하나 줄어요                if (need[w] == 0) queue.add(w);            }        }        System.out.println(order);    }}

using System;using System.Collections.Generic;using System.Linq; class Program{    static void Main()    {        int[] nm = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();        int n = nm[0], m = nm[1];        var adj = new List<int>[n + 1]; // adj[a] = a를 끝내야 시작할 수 있는 일들        for (int v = 0; v <= n; v++) adj[v] = new List<int>();        int[] need = new int[n + 1]; // need[b] = b보다 먼저 해야 하는데 아직 안 끝난 일의 수        for (int i = 0; i < m; i++)        {            int[] ab = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();            int a = ab[0], b = ab[1];            adj[a].Add(b);            need[b]++;        }         // 너비 우선 탐색: 1번 일에서 화살표를 가장 적게 몇 번 따라가면 닿는지        int[] dist = Enumerable.Repeat(-1, n + 1).ToArray(); // -1이면 아직 안 간 곳        dist[1] = 0;        var queue = new Queue<int>();        queue.Enqueue(1);        while (queue.Count > 0)        {            int v = queue.Dequeue();            foreach (int w in adj[v])            {                if (dist[w] == -1)                {                    dist[w] = dist[v] + 1; // 큐에 넣을 때 바로 적어요                    queue.Enqueue(w);                }            }        }        Console.WriteLine(string.Join(" ", dist.Skip(1)));         // 위상 정렬: 먼저 할 일이 남지 않은 일부터 꺼내요        var order = new List<int>();        for (int v = 1; v <= n; v++)        {            if (need[v] == 0) queue.Enqueue(v);        }        while (queue.Count > 0)        {            int v = queue.Dequeue();            order.Add(v);            foreach (int w in adj[v])            {                need[w]--; // v가 끝났으니 w가 기다리는 일이 하나 줄어요                if (need[w] == 0) queue.Enqueue(w);            }        }        Console.WriteLine(string.Join(" ", order));    }}

#include <iostream>#include <queue>#include <vector> int main() {    int n, m;    std::cin >> n >> m;    std::vector<std::vector<int>> adj(n + 1); // adj[a] = a를 끝내야 시작할 수 있는 일들    std::vector<int> need(n + 1, 0); // need[b] = b보다 먼저 해야 하는데 아직 안 끝난 일의 수    for (int i = 0; i < m; i++) {        int a, b;        std::cin >> a >> b;        adj[a].push_back(b);        need[b]++;    }     // 너비 우선 탐색: 1번 일에서 화살표를 가장 적게 몇 번 따라가면 닿는지    std::vector<int> dist(n + 1, -1); // -1이면 아직 안 간 곳    dist[1] = 0;    std::queue<int> queue;    queue.push(1);    while (!queue.empty()) {        int v = queue.front();        queue.pop();        for (int w : adj[v]) {            if (dist[w] == -1) {                dist[w] = dist[v] + 1; // 큐에 넣을 때 바로 적어요                queue.push(w);            }        }    }    for (int v = 1; v <= n; v++) std::cout << (v > 1 ? " " : "") << dist[v];    std::cout << '\n';     // 위상 정렬: 먼저 할 일이 남지 않은 일부터 꺼내요    std::vector<int> order;    for (int v = 1; v <= n; v++) {        if (need[v] == 0) queue.push(v);    }    while (!queue.empty()) {        int v = queue.front();        queue.pop();        order.push_back(v);        for (int w : adj[v]) {            need[w]--; // v가 끝났으니 w가 기다리는 일이 하나 줄어요            if (need[w] == 0) queue.push(w);        }    }    for (size_t i = 0; i < order.size(); i++) std::cout << (i > 0 ? " " : "") << order[i];    std::cout << '\n';}

#include <stdio.h> #define MAX 101 // 일은 100개까지라고 정해 둬요 int adj[MAX][MAX], deg[MAX]; // adj[a][0..deg[a]-1] = a를 끝내야 시작할 수 있는 일들int need[MAX]; // need[b] = b보다 먼저 해야 하는데 아직 안 끝난 일의 수int dist[MAX], queue[MAX], order[MAX]; int main(void) {    int n, m;    scanf("%d %d", &n, &m);    for (int i = 0; i < m; i++) {        int a, b;        scanf("%d %d", &a, &b);        adj[a][deg[a]++] = b;        need[b]++;    }     // 너비 우선 탐색: 1번 일에서 화살표를 가장 적게 몇 번 따라가면 닿는지    for (int v = 1; v <= n; v++) dist[v] = -1; // -1이면 아직 안 간 곳    dist[1] = 0;    int head = 0, tail = 0; // 큐: head에서 꺼내고 tail에 넣어요    queue[tail++] = 1;    while (head < tail) {        int v = queue[head++];        for (int i = 0; i < deg[v]; i++) {            int w = adj[v][i];            if (dist[w] == -1) {                dist[w] = dist[v] + 1; // 큐에 넣을 때 바로 적어요                queue[tail++] = w;            }        }    }    for (int v = 1; v <= n; v++) printf(v > 1 ? " %d" : "%d", dist[v]);    printf("\n");     // 위상 정렬: 먼저 할 일이 남지 않은 일부터 꺼내요    int count = 0;    head = tail = 0;    for (int v = 1; v <= n; v++) {        if (need[v] == 0) queue[tail++] = v;    }    while (head < tail) {        int v = queue[head++];        order[count++] = v;        for (int i = 0; i < deg[v]; i++) {            int w = adj[v][i];            need[w]--; // v가 끝났으니 w가 기다리는 일이 하나 줄어요            if (need[w] == 0) queue[tail++] = w;        }    }    for (int i = 0; i < count; i++) printf(i > 0 ? " %d" : "%d", order[i]);    printf("\n");    return 0;}

nm = コンソール.数読み();n = nm[0];m = nm[1];adj = 新リスト(n + 1, []); // adj[a] = a를 끝내야 시작할 수 있는 일들need = 新リスト(n + 1, 0); // need[b] = b보다 먼저 해야 하는데 아직 안 끝난 일의 수繰り返す (i = 0; i < m; i++){    ab = コンソール.数読み();    a = ab[0];    b = ab[1];    adj[a].追加(b);    need[b]++;} // 너비 우선 탐색: 1번 일에서 화살표를 가장 적게 몇 번 따라가면 닿는지dist = 新リスト(n + 1, -1); // -1이면 아직 안 간 곳dist[1] = 0;queue = [1];head = 0; // 큐의 맨 앞 자리. 꺼낼 때마다 한 칸씩 뒤로 가요間 (head < queue.個数){    v = queue[head];    head++;    それぞれ (w の中 adj[v])    {        もし (dist[w] == -1)        {            dist[w] = dist[v] + 1; // 큐에 넣을 때 바로 적어요            queue.追加(w);        }    }}コンソール.書く(dist.部分リスト(1, n).つなぐ(" ")); // 위상 정렬: 먼저 할 일이 남지 않은 일부터 꺼내요order = [];queue = [];head = 0;繰り返す (v = 1; v <= n; v++){    もし (need[v] == 0)    {        queue.追加(v);    }}間 (head < queue.個数){    v = queue[head];    head++;    order.追加(v);    それぞれ (w の中 adj[v])    {        need[w]--; // v가 끝났으니 w가 기다리는 일이 하나 줄어요        もし (need[w] == 0)        {            queue.追加(w);        }    }}コンソール.書く(order.つなぐ(" "));