一个群聊里有编号 1 到 n 的 n 个人。 每个人关注群里的其他若干人。 “a b”表示 a 关注 b，与 b 是否关注 a 无关。 i 号的人有一个标准 tᵢ。 每天早上，仍在群里的每个人数一数自己关注的人中还在群里的有几个。 这个数小于标准 tᵢ 的人，当天一起退出群聊。 同一天退出的人不是看到彼此才退出的，只按当天早上数出的数来决定。 退出的人不会再回来。 第一天早上所有人都在群里；一旦某天没有人退出，之后也不会再有人退出。 第一行输出留到最后的人数。 第二行按 1 号到 n 号输出每个人退出的那天（第一天为 1），留到最后的人输出 0。
输入
第一行给出 n 和关注关系数 m，第二行给出 t₁ … tₙ，接下来 m 行给出“a b”，用一个空格分隔。 1 ≤ n ≤ 10,000，0 ≤ m ≤ 30,000，0 ≤ tᵢ ≤ 10,000。 1 ≤ a, b ≤ n，a ≠ b，同样的“a b”不会出现两次（“a b”和“b a”可以同时出现）
输出
两行：留下的人数，以及每个人退出的那天共 n 个（用一个空格分隔）
样例 1 · stdin
6 6
1 2 1 0 1 2
1 2
2 1
2 3
3 5
6 4
6 1
stdout
1
4 3 2 0 1 5
main.py
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
每天把所有人重新数一遍，一天要 m 次，天数可达 n 天（排成一条链互相关注时是 10,000 天），共 3 亿次，太慢。 只看会变的人：保存 watching[v] = v 关注的人中还留着的数量，对今天退出的每个 u，只把关注 u 的人的数量各减 1。 为此要把“a b”反过来存，把 a 放进 followers[b] — 把 b 放进 a 的列表，就会去减 u 关注的人的数量，那是错的。 某人的数量第一次低于标准时，当场记为“明天退出”并放进明天的列表（与等今天退出的人全部离开后再数是一样的）。 每个人只能放进一次，所以已经退出或已定好要退出的人（day[w] != 0）不要再动 — 没有这个检查，同一个人会进列表两次，关注他的人的数量会减两次。 可以每天分开列表（今天、明天），也可以用一个队列并写 day[w] = day[u] + 1（和广度优先搜索一样的形状）。 例：5 号（不关注任何人，标准 1）第一天退出，关注 5 号的 3 号第二天退出，接着 2 号、1 号、6 号各晚一天退出，只有标准为 0 的 4 号留下。 陷阱一：每天从 1 号依次查看并当场让人退出，后面的编号当天就会感到前面编号的退出，日子会提前。 陷阱二：与标准相等就留下（是 <，不是 <=）。 邻接表各语言不同：Python [[] for _ in range(n)]（[[]] * n 是同一个列表指了 n 次），JavaScript/TypeScript Array.from({ length: n }, () => [])（new Array(n).fill([]) 也共用一个列表），Java List<List<Integer>>，C# List<int>[]，C++ std::vector<std::vector<int>>，C 用两个固定大小的数组做“起始位置 + 拼接列表”（CSR）。 Craykon 用 followers.添加([]) 做 n 次来建列表的列表 — 列表最多 10,000 项，所以 n 也最多 10,000。
Pythonmain.py · 33 行
import sysdata = sys.stdin.buffer.read().split()n, m = int(data[0]), int(data[1])need = [int(x) for x in data[2:2 + n]]followers = [[] for _ in range(n)] # followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장)watching = [0] * n # 지켜보는 사람 가운데 아직 방에 있는 수pos = 2 + nfor _ in range(m): a, b = int(data[pos]) - 1, int(data[pos + 1]) - 1 pos += 2 followers[b].append(a) watching[a] += 1day = [0] * n # 나간 날(0은 끝까지 남음)today = [v for v in range(n) if watching[v] < need[v]]for v in today: day[v] = 1d = 1while today: tomorrow = [] for u in today: # 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 for w in followers[u]: if day[w] == 0: # 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 watching[w] -= 1 if watching[w] < need[w]: day[w] = d + 1 # 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.append(w) today = tomorrow d += 1print(day.count(0))print(" ".join(map(str, day)))
JavaScriptmain.js · 36 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const need = data.slice(2, 2 + n);const followers = Array.from({ length: n }, () => []); // followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장)const watching = new Array(n).fill(0); // 지켜보는 사람 가운데 아직 방에 있는 수for (let i = 0; i < m; i++) { const a = data[2 + n + 2 * i] - 1; const b = data[3 + n + 2 * i] - 1; followers[b].push(a); watching[a]++;}const day = new Array(n).fill(0); // 나간 날(0은 끝까지 남음)let today = [];for (let v = 0; v < n; v++) { if (watching[v] < need[v]) { day[v] = 1; today.push(v); }}for (let d = 1; today.length > 0; d++) { const tomorrow = []; for (const u of today) { // 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 for (const w of followers[u]) { if (day[w] !== 0) continue; // 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 watching[w]--; if (watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.push(w); } } } today = tomorrow;}console.log(day.filter((x) => x === 0).length + "\n" + day.join(" "));
TypeScriptmain.ts · 38 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const need: number[] = data.slice(2, 2 + n);const followers: number[][] = Array.from({ length: n }, () => []); // followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장)const watching: number[] = new Array<number>(n).fill(0); // 지켜보는 사람 가운데 아직 방에 있는 수for (let i = 0; i < m; i++) { const a = data[2 + n + 2 * i] - 1; const b = data[3 + n + 2 * i] - 1; followers[b].push(a); watching[a]++;}const day: number[] = new Array<number>(n).fill(0); // 나간 날(0은 끝까지 남음)let today: number[] = [];for (let v = 0; v < n; v++) { if (watching[v] < need[v]) { day[v] = 1; today.push(v); }}for (let d = 1; today.length > 0; d++) { const tomorrow: number[] = []; for (const u of today) { // 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 for (const w of followers[u]) { if (day[w] !== 0) continue; // 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 watching[w]--; if (watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.push(w); } } } today = tomorrow;}console.log(day.filter((x) => x === 0).length + "\n" + day.join(" "));
JavaMain.java · 58 行
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; st.nextToken(); int m = (int) st.nval; int[] need = new int[n]; for (int v = 0; v < n; v++) { st.nextToken(); need[v] = (int) st.nval; } // followers.get(b) = b를 지켜보는 사람들(화살표를 거꾸로 저장) List<List<Integer>> followers = new ArrayList<>(); for (int v = 0; v < n; v++) followers.add(new ArrayList<>()); int[] watching = new int[n]; // 지켜보는 사람 가운데 아직 방에 있는 수 for (int i = 0; i < m; i++) { st.nextToken(); int a = (int) st.nval - 1; st.nextToken(); int b = (int) st.nval - 1; followers.get(b).add(a); watching[a]++; } int[] day = new int[n]; // 나간 날(0은 끝까지 남음) List<Integer> today = new ArrayList<>(); for (int v = 0; v < n; v++) { if (watching[v] < need[v]) { day[v] = 1; today.add(v); } } for (int d = 1; !today.isEmpty(); d++) { List<Integer> tomorrow = new ArrayList<>(); for (int u : today) { // 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 for (int w : followers.get(u)) { if (day[w] != 0) continue; // 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 if (--watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.add(w); } } } today = tomorrow; } int stay = 0; StringBuilder sb = new StringBuilder(); for (int v = 0; v < n; v++) { if (day[v] == 0) stay++; sb.append(day[v]).append(v + 1 < n ? ' ' : '\n'); } System.out.print(stay + "\n" + sb); }}
C#Main.cs · 51 行
using System;using System.Collections.Generic;using System.Linq;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int n = data[0], m = data[1]; int[] need = data[2..(2 + n)]; var followers = new List<int>[n]; // followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장) for (int v = 0; v < n; v++) followers[v] = new List<int>(); var watching = new int[n]; // 지켜보는 사람 가운데 아직 방에 있는 수 for (int i = 0; i < m; i++) { int a = data[2 + n + 2 * i] - 1, b = data[3 + n + 2 * i] - 1; followers[b].Add(a); watching[a]++; } var day = new int[n]; // 나간 날(0은 끝까지 남음) var today = new List<int>(); for (int v = 0; v < n; v++) { if (watching[v] < need[v]) { day[v] = 1; today.Add(v); } } for (int d = 1; today.Count > 0; d++) { var tomorrow = new List<int>(); foreach (int u in today) // 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 { foreach (int w in followers[u]) { if (day[w] != 0) continue; // 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 if (--watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.Add(w); } } } today = tomorrow; } Console.Write(day.Count(x => x == 0) + "\n" + string.Join(' ', day) + "\n"); }}
C++main.cpp · 41 行
#include <iostream>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<int> need(n); for (int &x : need) std::cin >> x; std::vector<std::vector<int>> followers(n); // followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장) std::vector<int> watching(n, 0); // 지켜보는 사람 가운데 아직 방에 있는 수 for (int i = 0; i < m; i++) { int a, b; std::cin >> a >> b; followers[b - 1].push_back(a - 1); watching[a - 1]++; } std::vector<int> day(n, 0); // 나간 날(0은 끝까지 남음) std::vector<int> today; for (int v = 0; v < n; v++) if (watching[v] < need[v]) day[v] = 1, today.push_back(v); int left = 0; for (int d = 1; !today.empty(); d++) { left += static_cast<int>(today.size()); std::vector<int> tomorrow; for (int u : today) { // 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 for (int w : followers[u]) { if (day[w] != 0) continue; // 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 if (--watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.push_back(w); } } } today.swap(tomorrow); } std::cout << n - left << '\n'; for (int v = 0; v < n; v++) std::cout << day[v] << (v + 1 < n ? ' ' : '\n');}
Cmain.c · 43 行
#include <stdio.h>#include <stdlib.h>int main(void) { int n, m; if (scanf("%d %d", &n, &m) != 2) return 0; int *need = malloc(sizeof(int) * n); for (int v = 0; v < n; v++) scanf("%d", &need[v]); int *ea = malloc(sizeof(int) * (m + 1)), *eb = malloc(sizeof(int) * (m + 1)); int *watching = calloc(n, sizeof(int)); /* 지켜보는 사람 가운데 아직 방에 있는 수 */ int *start = calloc(n + 1, sizeof(int)); /* 거꾸로 된 인접 목록(CSR): b를 지켜보는 사람들이 who[start[b] .. start[b+1]) */ for (int i = 0; i < m; i++) { scanf("%d %d", &ea[i], &eb[i]); ea[i]--, eb[i]--; watching[ea[i]]++; start[eb[i] + 1]++; } for (int v = 0; v < n; v++) start[v + 1] += start[v]; int *fill = malloc(sizeof(int) * (n + 1)), *who = malloc(sizeof(int) * (m + 1)); for (int v = 0; v <= n; v++) fill[v] = start[v]; for (int i = 0; i < m; i++) who[fill[eb[i]]++] = ea[i]; int *day = calloc(n, sizeof(int)); /* 나간 날(0은 끝까지 남음) */ int *queue = malloc(sizeof(int) * n); /* 나간 차례: 날이 같은 사람끼리 이어져 있다 */ int head = 0, tail = 0; for (int v = 0; v < n; v++) if (watching[v] < need[v]) day[v] = 1, queue[tail++] = v; while (head < tail) { int u = queue[head++]; for (int j = start[u]; j < start[u + 1]; j++) { /* u를 지켜보던 사람들의 수가 준다 */ int w = who[j]; if (day[w] != 0) continue; /* 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 */ if (--watching[w] < need[w]) { day[w] = day[u] + 1; /* u의 날에 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 */ queue[tail++] = w; } } } printf("%d\n", n - tail); for (int v = 0; v < n; v++) printf("%d%c", day[v], v + 1 < n ? ' ' : '\n'); free(need), free(ea), free(eb), free(watching), free(start), free(fill), free(who), free(day), free(queue); return 0;}
Craykonmain.cray · 55 行
첫줄 = 控制台.读数字();n = 첫줄[0];m = 첫줄[1];need = 控制台.读数字();followers = []; // followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장). 번호에서 1을 빼 0번부터 둔다循环 (v = 0; v < n; v++){ followers.添加([]);}watching = 新列表(n, 0); // 지켜보는 사람 가운데 아직 방에 있는 수循环 (i = 0; i < m; i++){ e = 控制台.读数字(); a = e[0] - 1; b = e[1] - 1; followers[b].添加(a); watching[a] += 1;}day = 新列表(n, 0); // 나간 날(0은 끝까지 남음)today = [];循环 (v = 0; v < n; v++){ 如果 (watching[v] < need[v]) { day[v] = 1; today.添加(v); }}d = 1;남은수 = n;当 (today.数量 > 0){ 남은수 -= today.数量; tomorrow = []; 遍历 (u 在 today) { 遍历 (w 在 followers[u]) { 如果 (day[w] == 0) { watching[w] -= 1; 如果 (watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.添加(w); } } } } today = tomorrow; d += 1;}控制台.输出(남은수);控制台.输出(day);