Không giống đếm tham chiếu, thuật toán Mark-and-Sweep xử lý được cả các đối tượng nằm trong chu trình tham chiếu lẫn nhau nhưng không còn được truy cập từ chương trình.
Cho n đối tượng đánh số 1..n và m cạnh có hướng biểu diễn con trỏ giữa các đối tượng (có thể tạo thành chu trình, có thể có cạnh trỏ tới chính nó). Cho k đối tượng GỐC (GC roots) — các đối tượng được chương trình truy cập trực tiếp.
Yêu cầu: thực hiện pha Mark (đánh dấu tất cả đối tượng có thể tới được từ các gốc bằng cách đi theo các cạnh có hướng, số bước bất kỳ kể cả 0 bước) và pha Sweep (thu hồi mọi đối tượng KHÔNG được đánh dấu).
Ví dụ: n=5 đối tượng, cạnh 1→2, 2→1 (chu trình), 3→4; gốc là {1,5}. Đối tượng 3,4 không có đường đi từ gốc nên bị thu hồi dù 3→4 vẫn còn cạnh với nhau — đây chính là trường hợp mà đếm tham chiếu đơn thuần KHÔNG xử lý được (không có chu trình ở đây, nhưng 3,4 vẫn là rác vì không gốc nào trỏ tới).
Dòng đầu: hai số nguyên n, m (1≤n≤2000, 0≤m≤5000).
m dòng tiếp theo, mỗi dòng u v (1≤u,v≤n) nghĩa là đối tượng u có con trỏ trỏ tới v.
Dòng tiếp theo: số nguyên k (0≤k≤n).
Dòng tiếp theo LUÔN có mặt (có thể là dòng trống nếu k=0): k số nguyên là định danh các đối tượng gốc.
In 3 dòng:
Với ví dụ trên, kết quả là:
2
3 4
1 2 5
Ví dụ:
Đầu vào:
5 3
1 2
2 1
3 4
2
1 5
Đầu ra:
2
3 4
1 2 5
Đầu vào:
2 0
0
Đầu ra:
2
1 2
Đang tải editor...