graphs (adjacency lists)queueP0278

A group chat you leave when the people you watch are gone

A group chat has n people, numbered 1 to n. Each person watches some of the other people in the chat.
"a b" means a watches b, regardless of whether b watches a. Person i has a threshold tᵢ. Every morning, each person still in the chat counts how many of the people they watch are still in the chat. Everyone whose count is less than their threshold tᵢ leaves the chat together that day. People leaving on the same day do not react to each other; it is decided only by the counts taken that morning. A person who leaves never comes back. On the first morning everyone is in the chat, and once a day comes when nobody leaves, nobody leaves after that either. On the first line print the number of people who stay to the end. On the second line print, for each person from 1 to n, the day they left (the first day is 1), or 0 for someone who stays to the end.

Input: The first line has n and the number of watching relations m, the second line t₁ … tₙ, and the next m lines "a b", separated by single spaces.
1 ≤ n ≤ 10,000, 0 ≤ m ≤ 30,000, 0 ≤ tᵢ ≤ 10,000.
1 ≤ a, b ≤ n, a ≠ b, and the same "a b" never appears twice ("a b" and "b a" may both appear)
Output: Two lines: the number of people who stay, and the n leaving days (separated by single spaces)

Example 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 Programming language Runtime version

Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

Recounting everyone each day costs m per day, and there can be up to n days (10,000 when people watch each other in a single line), 300 million steps — too slow.
Look only at people who change: keep watching[v] = how many people v watches are still in, and for each u who left today, decrease by 1 only the counts of the people who watched u.
For that, store "a b" reversed, putting a into followers[b] — putting b into a's list makes you decrease the counts of the people u watched, which is wrong.
When someone's count first drops below the threshold, mark them 'leaves tomorrow' right then and put them on tomorrow's list (the same as counting after everyone who left today is gone).
Each person must go in only once, so skip anyone who already left or is already set to leave (day[w] != 0) — without this check the same person enters the list twice and the counts of the people watching them drop twice.
You may keep a list per day (today and tomorrow), or use one queue and write day[w] = day[u] + 1 (the shape of a breadth-first search).
Example: person 5 (watches nobody, threshold 1) leaves on day 1, person 3 who watched 5 on day 2, then persons 2, 1 and 6 each a day later, and only person 4 with threshold 0 stays.
Trap one: going through people from 1 each day and removing them on the spot lets later numbers feel an earlier number leaving the same day, so days come too early.
Trap two: equal to the threshold stays (<, not <=).
Adjacency lists differ by language: Python [[] for _ in range(n)] ([[]] * n points to one list n times), JavaScript/TypeScript Array.from({ length: n }, () => []) (new Array(n).fill([]) also shares one list), Java List<List<Integer>>, C# List<int>[], C++ std::vector<std::vector<int>>, and C builds 'start positions + one joined list' (CSR) from two fixed-size arrays.
Craykon builds the list of lists with followers.Add([]) n times — lists hold up to 10,000 items, so n goes up to 10,000.

Pythonmain.py · 33 lines

import sys data = 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] += 1 day = [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 += 1 print(day.count(0))print(" ".join(map(str, day)))

JavaScriptmain.js · 36 lines

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 lines

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 lines

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 lines

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 lines

#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 lines

#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 lines

첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];need = Console.ReadNumbers();followers = []; // followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장). 번호에서 1을 빼 0번부터 둔다for (v = 0; v < n; v++){    followers.Add([]);}watching = NewList(n, 0); // 지켜보는 사람 가운데 아직 방에 있는 수for (i = 0; i < m; i++){    e = Console.ReadNumbers();    a = e[0] - 1;    b = e[1] - 1;    followers[b].Add(a);    watching[a] += 1;} day = NewList(n, 0); // 나간 날(0은 끝까지 남음)today = [];for (v = 0; v < n; v++){    if (watching[v] < need[v])    {        day[v] = 1;        today.Add(v);    }}d = 1;남은수 = n;while (today.Count > 0){    남은수 -= today.Count;    tomorrow = [];    foreach (u in today)    {        foreach (w in followers[u])        {            if (day[w] == 0)            {                watching[w] -= 1;                if (watching[w] < need[w])                {                    day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다                    tomorrow.Add(w);                }            }        }    }    today = tomorrow;    d += 1;}Console.WriteLine(남은수);Console.WriteLine(day);