FACEFRND - Friends of Friends

Link đề bài trên SPOJ

Đề bài:

Bob hay lên mạng xã hội chơi và giờ Bob đang thắc mắc: không biết khai niệm "Bạn của Bạn (Friends of Friends)" trong mạng xã hội đó là sao? Nếu $X$ là bạn của Bob, $Y$ là bạn của $X$ nhưng $Y$ không phải là bạn của Bob thì $Y$ là một người "Bạn của Bạn" của Bob. Bạn được yêu cầu tìm số lượng người "Bạn của Bạn" của Bob. (Mỗi người trong mạng xã hội đó được định danh bằng một ID 4 chữ số).

Input:

Dòng đầu tiên chứa một số nguyên $N\ (1 \leq N \leq 1000)$ là số lượng người trong danh sách bạn bè của Bob. Tiếp sau đó là $N$ dòng:

• Đầu mỗi dòng là ID người bạn của Bob.
• Tiếp sau đó là số nguyên $M\ (1 \leq M \leq 100)$ là số lượng người trong danh sách bạn bè của người đó.
• Tiếp sau đó là $M$ ID lần lượt là ID của từng người bạn (ngoại trừ Bob).

Output:

In ra một số nguyên duy nhất - số lượng người "Bạn của Bạn" của Bob.

Ví dụ:

Input:

$3$
$2334$ $5$ $1256$ $4323$ $7687$ $3244$ $5678$
$1256$ $2$ $2334$ $7687$
$4323$ $5$ $2334$ $5678$ $6547$ $9766$ $9543$

Output:

$6$

Hướng dẫn giải

Từ ví dụ bên trên, ta có thể chỉ ra được những người "Bạn của Bạn" trong ví dụ là $3244, 5678, 6547, 7687, 9543$ và $9766$. Tổng quát về cách giải: ta ghi những ID là bạn của Bob (ID đầu tiên mỗi dòng) vào 1 mảng, ghi những ID còn lại vào một mảng. Nếu ID trong mảng bạn Bob tồn tại trong mảng còn lại thì ID đó không được tính là "Bạn của Bạn".

Bài này tiện nhất là dùng STL set vì tìm kiếm sẽ nhanh hơn, kiểu dữ liệu cũng nên để là string thay vì int vì ID vẫn có thể có số 0 ở đầu. Code mẫu mình để ở đây.

Chốt:

Happy coding!