[test] Nguồn: TopCoder Người dịch: T Disjoint Sets là cấu trúc dữ liệu hữu ích được sử dụng thường xuyên trong các cuộc thi, từ VOI (Vietnam Olympiad Informatics) đến IOI (International Informatics Olympiad). Bài viết này sẽ đưa ra các cách cài đặt Disjoint Sets hiệu quả và nhanh nhất. Bài toán Mở đầu, ta hãy xét bài toán sau: ::: info

Nguồn: TopCoder Người dịch: T Disjoint Sets là cấu trúc dữ liệu hữu ích được sử dụng thường xuyên trong các cuộc thi, từ VOI (Vietnam Olympiad Informatics) đến IOI (International Informatics Olympiad). Bài viết này sẽ đưa ra các cách cài đặt Disjoint Sets hiệu quả và nhanh nhất. Bài toán Mở đầu, ta hãy xét bài toán sau: ::: info Trong một phòng có $N$ người, ta định nghĩa hai người là bạn nếu họ là bạn bè trực tiếp của nhau hoặc gián tiếp là bạn của nhau. Bạn gián tiếp có nghĩa là nếu $A$ là bạn với $B$, và $B$ là bạn với $C$, thì $A$ cũng là bạn với $C$. Một nhóm bạn là một nhóm mà hai người bất kỳ trong nhóm là bạn. Đưa ra danh sách những người là bạn bè trực tiếp với nhau, hãy tìm số nhóm bạn và số người trong mỗi nhóm. :::

//Thảo Phạm Nguồn dịch: http://www.usaco.org/index.php?page=viewproblem2&cpid=1134 --------- MÊ CUNG TAC TOE Cô bò sữa Bessie rất thích giải các mê cung. Cô ấy cũng thích chơi tic-tac-toe (hay đúng hơn là một phiên bản bò của tic-tac-toe, sẽ được miêu tả bên dưới). Bác nông dân John đã tìm ra một cách mới cho cô ấy để chơi cả hai trò chơi cùng một lúc! Đầu tiên, tic-tac-toe bò: thay vì đặt những chữ X và chữ O trên một lưới 3 × 3, những chú bò sẽ chơi với những chữ M và chữ O trên một lưới 3 × 3. Trong mỗi lượt, người chơi đặt chữ M hoặc chữ O trên một trong các ô trống của lưới (đây là một điểm khác biệt khác với tic-tac-toe cổ điển, nơi một người chơi chỉ luôn đặt chữ X và người còn lại chỉ luôn đặt chữ O). Người chiến thắng trò chơi này là người chơi đầu tiên viết MOO, theo chiều ngang, chiều dọc hoặc đường chéo. Trò chơi cho phép viết ngược chữ, ví dụ như người chơi có thể thắng bằng cách viết OOM trên một trong các đường lưới. Cũng giống như trong tic-tac-toe cổ điển, có khả năng xảy ra bảng với tình trạng không có người chiến thắng. Một bước di chuyển tic-tac-toe bò được xác định bằng 3 ký tự Mij hoặc Oij, trong đó i và j là số nguyên trong phạm vi từ 1 đến 3, xác định hàng và cột của ô để đặt ký tự M hoặc O tương ứng. Để thách thức Bessie, bác nông dân John đã thiết kế một mê cung hình vuông trên một lưới N × N (3 ≤ N ≤ 25). Một số ô, bao gồm tất cả các ô ở biên giới cạnh, chứa các kiện cỏ khô lớn, ngăn không cho Bessie di chuyển đến các ô đó. Bessie có thể di chuyển tự do trên tất cả các ô khác trong mê cung bằng cách thực hiện các bước theo bốn hướng thông thường là bắc, nam, đông, tây. Một số ô chứa một mảnh giấy trên đó có ghi một nước đi tic-tac-toe bò. Trong khi di chuyển qua mê cung, bất cứ khi nào cô ấy đi qua một ô có chứa mảnh giấy, Bessie phải chơi nước đi tương ứng trong trò chơi tic-tac-toe bò mà cô ấy đang chơi đồng thời (trừ trường hợp ô vuông tương ứng trong trò chơi tic-tac-toe đã bị đánh dấu, khi đó cô ấy không cần hành động gì). Cô ấy không có đối thủ trong trò chơi tic-tac-toe phiên bản của bò này, nhưng một số ô trong mê cung có thể là trở ngại của cô ấy với mục tiêu cuối cùng là đánh vần MOO.