Elearning CodePath – CTP Online Judge

Tìm người nổi tiếng

CELEBRITY

🟢 Hard #Graph #Two Pointers #Stack #Interval

### Thông tin chung
Tên bài toán: Tìm người nổi tiếng (The Celebrity Problem)
Nguồn: Bài toán đồ thị / Tư duy logic/stack/2 con tro
Tên file input: CELEB.INP
Tên file output: CELEB.OUT

### Bài toán
Trong một bữa tiệc có n người, được đánh số từ 0 đến n - 1. Ta có thông tin về mối quan hệ giữa họ thông qua một ma trận vuông nhị phân mat kích thước n x n. Trong đó:
- mat[i][j] = 1: Người i biết người j.
- mat[i][j] = 0: Người i không biết người j.

Một người được gọi là người nổi tiếng (celebrity) nếu thỏa mãn đồng thời hai điều kiện:
1. Tất cả mọi người khác đều biết người này.
2. Người này không biết bất kỳ ai khác.

Yêu cầu: Hãy xác định chỉ số của người nổi tiếng trong bữa tiệc. Nếu không tồn tại người nào như vậy, hãy in ra -1.

Lưu ý: Trong bữa tiệc chỉ có tối đa một người nổi tiếng. Giá trị mat[i][i] không ảnh hưởng đến kết quả.

### Định dạng đầu vào
Dữ liệu đọc từ file CELEB.INP:
- Dòng đầu tiên chứa số nguyên n (1 <= n <= 10^4).
- n dòng tiếp theo, mỗi dòng chứa n số nguyên (0 hoặc 1) cách nhau bởi dấu cách, mô tả ma trận mat.

### Định dạng đầu ra
Ghi ra file CELEB.OUT:
- Một số nguyên duy nhất là chỉ số của người nổi tiếng (theo 0-based indexing) hoặc -1.

### Ví dụ
Input:
3
1 1 0
0 1 0
0 1 1

Output:
1

Giải thích:
- Người 0 biết người 1.
- Người 2 biết người 1.
- Người 1 không biết người 0 và người 2.
=> Người 1 là người nổi tiếng.

### Subtasks
- Subtask 1 (50% số điểm): n <= 200.
- Subtask 2 (50% số điểm): n <= 10^4.

✅ Đã AC: 0 / 2 submissions