SPOJ.COM – Thuật toán bài FACEFRND - Friends of Friends
Đề bài:
Bob dùng trang mạng xã hội hầu hết thời gian. Anh ấy đã tò mò về vấn đề bạn của bạn trên trang mạng xã hội này. Nếu như X là bạn anh ấy. Và Y là bạn của X. Mà Y không phải bạn của anh ấy. Khi đó Y được gọi là bạn của bạn. Bạn phải tìm ra xem Bob có bao nhiêu bạn của bạn. Biết các ID được dùng trên mạng xã hội là số duy nhất bao gồm 4 chữ số.
Đầu vào:
Dòng đầu tiên là số nguyên N, 1 <= N <= 100 - là số bạn trên trang mạng xã hội của Bob. Sau đó là N dòng. Số đầu tiên của mỗi dòng là ID của bạn Bob và sau đó là số M (1 <= M <= 100) là số bạn của anh ta. Sau đó là M số nguyên là ID của những người bạn (không bao gồm Bob).
Đầu ra:
In ra một số nguyên xác định số bạn của bạn của Bob.
Ví dụ:
Đầu vào:
3
2334 5 1256 4323 7687 3244 5678
1256 2 2334 7687
4323 5 2334 5678 6547 9766 9543
Đầu ra:
6
Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/FACEFRND/
Phân tích:
-
Bài toán có vẻ khá rõ ràng. Ở đây tôi sử dụng thuật toán tham lam Greedy để giải bài toán. Tôi sẽ thực hiện đúng như trong đề bài. Đó là tìm ra những người là bạn của bạn Bob.
-
Vì ID là một số duy nhất có 4 chữ số nên tôi sử dụng mảng đánh dấu gồm 10000 phần tử để đánh dấu trạng thái của các ID là bạn của Bob hay không, và đã xuất hiện chưa.
-
Mời bạn theo dõi code sau để hiểu rõ hơn về cách triển khai của tôi.
Lời giải:
(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/C++:
| #include<iostream> | |
| using namespace std; | |
| const int MAX = 10005; | |
| bool exist[MAX]; // Đánh dấu xem tồn tại hay chưa | |
| bool friend_bob[MAX]; // có phải bạn của Bob không | |
| int main() | |
| { | |
| // Khởi tạo giá trị là false | |
| for(int i = 0; i < MAX; i++) | |
| { | |
| exist[i] = false; | |
| friend_bob[i] = false; | |
| } | |
| // đếm số lượng bạn của bạn | |
| int cnt_fof = 0; | |
| int n = 0; | |
| cin >> n; | |
| for(int i = 0; i < n; i++) | |
| { | |
| int id_fob = 0; | |
| cin >> id_fob; | |
| if(exist[id_fob]) | |
| { | |
| cnt_fof--; | |
| } | |
| friend_bob[id_fob] = true; | |
| int m = 0; | |
| cin >> m; | |
| for(int j = 0; j < m; j++) | |
| { | |
| int id_fof = 0; | |
| cin >> id_fof; | |
| // Kiểm tra ID của bạn của bạn Bob xem có phải bạn của Bob không | |
| // và đã tồn tại hay chưa. | |
| // Nếu thỏa mãn thì đánh dấu là đã tồn tại để khỏi bị lặp và tăng biến đếm lên | |
| if(friend_bob[id_fof] == false && exist[id_fof] == false) | |
| { | |
| exist[id_fof] = true; | |
| cnt_fof++; | |
| } | |
| } | |
| } | |
| cout << cnt_fof << endl; | |
| return 0; | |
| } |
Code by Phạm Văn Lâm.