Nguồn: http://vn.spoj.com/problems/NKGUARD/
Solution:
Solution:
Ý tưởng giải thuật: Ta sẽ làm 2 bước:
Bước 1: Với mỗi đỉnh [i,j] chưa thăm, ta dfs đánh dấu các đỉnh có chiều
cao < a[i,j], ta sẽ đảm bảo rằng từ đỉnh có chiều cao a[u,v] nào đó, thủ tục
dfs1 sẽ đánh dấu những đỉnh có chiều cao ≤ a[u,v] lận cận;
Như vậy chỉ có các đỉnh có chiều cao “đỉnh” còn lại;
Bước 2: Dfs để tìm các nhóm đỉnh, thực chất Dfs lần này là để đếm số lượng
thành phần liên thông
Chương trình tham khảo:
