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

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 mình sử dụng thuật toán tham lam Greedy để giải bài toán. Mình 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 mình 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 mình.

Lời giải

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 mình 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 mình 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 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;
}