Covid (ICTU P58)

Nguồn: laptrinh.ictu.edu.vn Độ khó: Trung bình Đồ thị Loang (BFS/DFS) Mảng đánh dấu

Đề bài

Giới hạn thời gian: 2 giây  ·  Giới hạn bộ nhớ: 512 MB

Hải đang làm việc tại một tập đoàn đa quốc gia có $n$ nhân viên được đánh mã số thứ tự từ $1$ đến $n$. Mỗi người có một phòng làm việc riêng của mình. Do nhu cầu công việc, hàng ngày mỗi nhân viên có thể phải tiếp xúc với một số nhân viên khác. Vào một ngày đẹp trời, Hải bị nhiễm Covid, nhưng do không biết nên Hải vẫn đi làm. Đến cuối ngày người ta mới phát hiện ra Hải là người nhiễm Covid đầu tiên. Khả năng lây lan của Covid rất nhanh chóng, một người nhiễm bệnh nếu tiếp xúc với một người khác có thể sẽ truyền bệnh cho người này, chính vì thế hiện tại thế giới đã có hơn 63 triệu người nhiễm bệnh.

Hãy giúp các bác sĩ kiểm tra xem cuối ngày hôm đó, có tối đa bao nhiêu người có thể sẽ nhiễm bệnh và đó là những người nào để còn cách ly. Người có tiếp xúc với người nhiễm bệnh được coi là người nhiễm bệnh.

Đầu vào:

• Dòng đầu tiên ghi 2 số tự nhiên $n, k$ $(1 \le n \le 10^5,\ 1 \le k \le n)$ tương ứng là số lượng người làm việc trong toà nhà và mã số của nhân viên đã nhiễm Covid đầu tiên.
• Dòng thứ $i$ trong $n$ dòng tiếp theo ghi danh sách những người có tiếp xúc với người thứ $i$ theo cách sau: số đầu tiên $m$ của dòng là tổng số nhân viên đã gặp người thứ $i$, tiếp theo là $m$ số tự nhiên lần lượt là số hiệu của các nhân viên đó. Nếu $m = 0$ có nghĩa rằng $i$ không tiếp xúc với ai.
• Dữ liệu được cho đảm bảo tổng số lần tiếp xúc của tất cả nhân viên trong cơ quan không vượt quá $10^6$.

Đầu ra:

• Dòng đầu tiên ghi số $s$ là tổng số người có thể bị lây nhiễm Covid.
• Dòng thứ 2 liệt kê tất cả nhân viên có thể bị lây nhiễm Covid cần cách ly, danh sách cần được sắp theo thứ tự tăng dần của số hiệu nhân viên.

Ví dụ – input

5 1
2 2 3
2 1 3
2 1 2
1 5
1 4

Ví dụ – output

3
1 2 3

Lời mở đầu

Bài này nhìn vào là thấy ngay dạng bài áp dụng thuật toán BFS (duyệt theo chiều rộng), hay có thể gọi nôm na là thuật toán loang. Bạn nào đã biết thuật toán này thì giải bài này khá đơn giản, còn chưa biết thì sẽ hơi khó một chút. Nên trong bài viết mình sẽ giải thích kỹ thuật toán loang trước rồi mới vào code nhé 😇.

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Có $n = 5$ nhân viên, người nhiễm đầu tiên là $k = 1$. Đọc 5 dòng tiếp theo:

Dòng	Người	Số người đã gặp $m$	Đã gặp những ai
2 2 3	1	2	2, 3
2 1 3	2	2	1, 3
2 1 2	3	2	1, 2
1 5	4	1	5
1 4	5	1	4

Người $1$ nhiễm bệnh, đã gặp người $2$ và $3$ ⇒ $2$, $3$ cũng bị coi là nhiễm. Người $2$, $3$ lại chỉ gặp nhau và gặp người $1$ – không lây thêm ai mới. Còn người $4$ và $5$ chỉ gặp nhau, không dính dáng gì tới nhóm $\{1, 2, 3\}$ nên an toàn. Vậy có $3$ người cần cách ly: 1 2 3.

Lưu ý

Bài này không chỉ có F1 đâu nhé: người nhiễm lây cho F1, F1 lại lây cho F2, F2 lây cho F3... cứ thế đến khi không còn ai mới. Nên không thể chỉ in danh sách những người gặp trực tiếp người $k$ được.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Ý tưởngThuật toán loang là gì?Cách 1Loang từ người k + sắp xếp · O(N log N + M)

Ý tưởngThuật toán loang là gì?

Nói nhanh cho bạn nào chưa biết: thuật toán loang các bạn cứ tưởng tượng một ly nước đổ trên mặt phẳng, nước sẽ cứ lan rộng ra đến khi nào không lan được nữa thì thôi (gặp vật cản). Làm sao để biết nó còn lan được tới đâu? Đơn giản thôi:

1. Tại vị trí ban đầu, ta xem nó lan ra được những vị trí nào, đưa hết các vị trí đó vào một hàng đợi.
2. Lấy lần lượt từng vị trí trong hàng đợi ra, lại xem vị trí đó còn lan được ra những đâu, đưa tiếp vào hàng đợi.
3. Cứ thế lặp lại đến khi hàng đợi rỗng – nghĩa là không lan thêm được nữa – thì thuật toán kết thúc.

Suốt quá trình đó, chỗ nào lan tới được thì ta đánh dấu lại, nhìn vào là biết nước đã lan tới những đâu.

Tại sao bài này lại áp dụng thuật toán loang? Vì rõ ràng việc lây nhiễm chính là sự loang ra: 1 người lây cho 5 người, mỗi người trong 5 người đó lại lây cho mấy người khác nữa... bản chất là đang loang rộng ra. Nếu xem mỗi nhân viên là một đỉnh, mỗi lần tiếp xúc là một cạnh nối 2 đỉnh, thì đáp án chính là tất cả các đỉnh "loang" tới được từ đỉnh $k$.

Ý chính

Đáp án = tập các người có thể đi tới được từ người $k$ theo các lần tiếp xúc (kể cả $k$). Loang từ $k$, mỗi người chỉ được đưa vào hàng đợi đúng 1 lần nhờ mảng đánh dấu check.

Minh hoạ: Covid loang trong công ty

Em nhập số nhân viên $n$, người nhiễm đầu tiên $k$ và danh sách các cặp tiếp xúc (dạng u-v, cách nhau bởi dấu cách), rồi bấm Tiếp để xem dịch loang qua từng người. Khung này làm đúng như code bên dưới: lấy người ở cuối mảng temp ra xét.

n k tiếp xúc

Ví dụ nhanh:

n ≤ 12; mỗi cặp u-v nghĩa là u và v có gặp nhau (ghi vào danh sách của cả 2 người).

Cách 1Loang từ người k, đánh dấu và sắp xếp – O(N log N + M)

Cách giải quyết bài này như sau:

• Đọc dữ liệu: từ dòng thứ 2 trở đi ta đọc vào một mảng 2 chiều a, dòng a[i] chính là danh sách những người tiếp xúc với người thứ $i$. Nhờ vậy khi xét tới người có mã số $x$, ta lấy ngay được danh sách những người đã gặp $x$ là các phần tử trên dòng a[x]. Mình dùng vector<vector<int>> cho thuận tiện, và cho a[i] có m + 1 ô để dùng chỉ số từ $1$ đến $m$ (bỏ ô $0$).
• Mảng đánh dấu: bool check[n + 1] = {false} – ban đầu tất cả là false. Nhờ nó mà trong $O(1)$ ta biết ngay một mã số đã được đưa vào hàng đợi hay chưa, chỉ cần xem check tại chỉ số đó là true hay false.
• Loang: đưa người $k$ vào hàng đợi (nhớ đặt check[k] = true). Rồi liên tục lấy một người ra khỏi hàng đợi, người lấy ra là người đã nhiễm bệnh nên cho vào mảng kết quả res. Duyệt danh sách người đã gặp người đó: ai có check = false thì cập nhật check = true rồi mới đưa vào hàng đợi; ai check = true rồi thì thôi, kẻo bị trùng.
• In kết quả: khi hàng đợi rỗng, sắp xếp res tăng dần, in số lượng rồi in từng phần tử.

Vì sao "hàng đợi" của mình lại lấy ra ở cuối?

Mình dùng vector 1 chiều temp làm hàng đợi (vì muốn dùng toàn mảng để bạn nào chưa học tới queue thì không bỡ ngỡ). Đưa vào thì đưa ở cuối (push_back), nhưng lấy ra cũng lấy ở cuối luôn (back + pop_back). Bạn nào học hàng đợi rồi sẽ thấy mình làm hơi khác: theo đúng nguyên tắc hàng đợi thì phải lấy ra ở đầu (index $0$). Nhưng nếu xoá ở index $0$ thì toàn bộ các ô phía sau phải nhích lên, tốn $O(N)$ cho mỗi lần lấy; còn lấy ở cuối thì chỉ $O(1)$.

Thứ tự xét không quan trọng ở bài này

Ở bài này, hàng đợi chỉ để lưu lại cho ta xét hết tất cả, không bỏ sót ai bị lây. Ai xét trước, ai xét sau không ảnh hưởng tới đáp án, miễn là xét đủ – nên làm thế này hoàn toàn được. (Lấy ra ở cuối thì thực chất temp hoạt động như một ngăn xếp, kiểu loang theo chiều sâu – DFS – nhưng tập người loang tới được vẫn y hệt BFS.)

Khi nào thứ tự lại quan trọng?

Nếu đề hỏi kiểu "mỗi người là F mấy" hay tìm đường đi ngắn nhất, thì phải làm đúng nguyên tắc hàng đợi: ai vào trước thì lấy ra xét trước (dùng queue, hoặc giữ một biến chỉ số head chạy dần trên mảng thay vì xoá ở đầu).

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector< vector<int> > a;
    a.resize(n + 1);
    for(int i = 1; i <= n; ++i){
        int m;
        cin >> m;
        a[i].resize(m + 1);
        for(int j = 1; j <= m; ++j){
            cin >> a[i][j];
        }
    }
    vector<int> temp, res;
    bool check[n + 1] = {false};
    temp.push_back(k);
    check[k] = true;
    while(!temp.empty()){
        int idx = temp.back();
        temp.pop_back();
        res.push_back(idx);
        for(int j = 1; j < (int)a[idx].size(); ++j){
            int x = a[idx][j];
            if(check[x] == false){
                check[x] = true;
                temp.push_back(x);
            }
        }
    }
    cout << (int)res.size() << endl;
    sort(res.begin(), res.end());
    for(int i = 0; i < (int)res.size(); ++i){
        cout << res[i] << " ";
    }
    return 0;
}

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, k = data[0], data[1]
    pos = 2
    a = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        m = data[pos]
        a[i] = data[pos + 1:pos + 1 + m]
        pos += 1 + m
    check = [False] * (n + 1)
    temp = [k]
    check[k] = True
    res = []
    while temp:
        idx = temp.pop()
        res.append(idx)
        for x in a[idx]:
            if not check[x]:
                check[x] = True
                temp.append(x)
    res.sort()
    sys.stdout.write(str(len(res)) + "\n" + " ".join(map(str, res)) + "\n")

main()

Về bản Python

Dữ liệu có thể tới cỡ $10^6$ số nên bản Python đọc một lần toàn bộ input bằng sys.stdin.buffer.read() cho nhanh, thay vì gọi input() từng dòng.

C++▶ Chạy tay từng dòng codeĐọc danh sách tiếp xúc, loang từ người k bằng mảng temp (lấy ra ở cuối), đánh dấu check, sắp xếp res rồi in.

Dữ liệu vào (stdin) – sửa thoải mái5 1 2 2 3 2 1 3 2 1 2 1 5 1 4

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 int n, k;

8 cin >> n >> k;

9 vector< vector<int> > a;

10 a.resize(n + 1);

11 for(int i = 1; i <= n; ++i){

12 int m;

13 cin >> m;

14 a[i].resize(m + 1);

15 for(int j = 1; j <= m; ++j){

16 cin >> a[i][j];

17 }

18 }

19 vector<int> temp, res;

20 bool check[n + 1] = {false};

21 temp.push_back(k);

22 check[k] = true;

23 while(!temp.empty()){

24 int idx = temp.back();

25 temp.pop_back();

26 res.push_back(idx);

27 for(int j = 1; j < (int)a[idx].size(); ++j){

28 int x = a[idx][j];

29 if(check[x] == false){

30 check[x] = true;

31 temp.push_back(x);

32 }

33 }

34 }

35 cout << (int)res.size() << endl;

36 sort(res.begin(), res.end());

37 for(int i = 0; i < (int)res.size(); ++i){

38 cout << res[i] << " ";

39 }

40 return 0;

41}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này (gọi $N$ là số nhân viên, tối đa $10^5$; $M$ là tổng số lần tiếp xúc, tối đa $10^6$):

• Thời gian:
  • Đọc dữ liệu vào mảng 2 chiều: $O(N + M)$.
  • Loang: mỗi người vào hàng đợi tối đa 1 lần ($\le N$ lần), mỗi danh sách tiếp xúc được duyệt tối đa 1 lần (tổng $\le M$) ⇒ $O(N + M)$.
  • Sắp xếp res (tối đa $N$ phần tử) bằng sort: $O(N \log N)$, cỡ $10^5 \cdot 17 \approx 2 \cdot 10^6$. In ra: $O(N)$.
  Theo quy tắc cộng Big-O thì lấy thằng lớn nhất: $O(\max(N \log N,\ N + M))$, cỡ vài triệu phép tính. Giới hạn 2 giây (khoảng $10^8$ phép tính) nên yên tâm AC.
• Không gian: mảng 2 chiều a lưu tối đa $N + M$ số; temp, res, check mỗi cái tối đa $N$ phần tử ⇒ $O(M + 3N)$ = $O(N + M)$.

Không gian$O(N + M)$

Thời gian$O(N \log N + M)$

Đừng tự sắp xếp bằng O(N²)

Nếu ở bước sắp xếp bạn nào tự cài kiểu sắp xếp nổi bọt / chọn $O(N^2)$ thì với $N = 10^5$ cần cỡ $10^{10}$ phép tính – chắc chắn TLE. Dùng sort có sẵn là an toàn nhất. (Hoặc tinh ý hơn: sau khi loang xong, duyệt $i$ từ $1$ đến $n$ và in những ai có check[i] = true là đã được danh sách tăng dần, khỏi cần sắp xếp.)

Ghi chú của mình: code C++ và Python ở trên đã chạy đúng ví dụ của đề, và được kiểm tra với 500 bộ test ngẫu nhiên nhỏ ($n \le 12$, cả danh sách tiếp xúc đối xứng lẫn không đối xứng), so với một code vét cạn lặp "lây lan" cho tới khi không còn ai mới – khớp hết. Với test lớn $n = 10^5$ và khoảng $10^6$ lần tiếp xúc: bản C++ chạy khoảng 0.3–0.8 giây trên máy mình (tuỳ lần chạy, phần lớn là thời gian đọc dữ liệu), bản Python khoảng 4 giây – nên với giới hạn 2 giây, các bạn nộp bản C++ là chắc ăn nhất.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇