Ở ngôi làng nọ có N người được đánh số từ 1 đến N. Trong đó một số người có quan hệ huyết thống với nhau. Quan hệ huyết thống có tính bắc cầu nên nếu A và B có quan hệ huyết thống, B và C có quan hệ

2024-11-14 08:55:34

Ở ngôi làng nọ có N người được đánh số từ 1 đến N. Trong đó một số người có quan hệ huyết thống với nhau. Quan hệ huyết thống có tính bắc cầu nên nếu A và B có quan hệ huyết thống, B và C có quan hệ huyết thống thi A và C cũng có quan hệ huyết thông với nhau. Tất cả những người có cùng quan hệ huyết thống với nhau tạo thành mỏi gia đình. Một người không có quan hệ huyết thống với bất kỳ ai cũng được xem như là 1 gia đình. Người ta đã thống kẻ được M cặp đôi (2 người) có cùng huyết thống và từ đó biết được các gia đình ở trong làng. Họ cũng kết luận rằng những gia đình có số lượng người không phải là số nguyên tổ thì chắc chắn là những gia đình hạnh phúc, Yêu cầu: Hãy đếm số lượng gia đình chắc chắn là gia đình hạnh phúc trong ngôi lang. Dữ liệu vào: Cho trong tệp văn bản HAPPY.INP có cấu trúc như sau: - Dòng đầu tiên chứa 2 số N, M cách nhau 1 ký tự trắng. (Điều kiện: 1 <= n <= 500, 1 <= m <= 5000); - M dòng tiếp theo mỗi dòng ghi 2 số nguyên x và y cách nhau 1 ký tự trắng với ý nghĩa là người thứ 6 có quan hệ huyết thống với người thứ y (1<=x,y<=N), Dữ liệu ra: Ghi ra tập văn bản HAPPYOUT một số nguyên duy nhất là số lượng gia đình chắc chắn là gia đình hạnh phúc trong ngôi làng. input 9 5 1 5 2 6 3 5 4 7 1 9 output 2. C++ nhé

Câu trả lời này dùng AI, hãy kiểm tra lại trước khi sử dụng

```cpp
#include
#include
#include
#include

using namespace std;

vector parent(501); // Tìm đại diện của mỗi người
vector size(501, 1); // Kích thước của mỗi gia đình

// Hàm để tìm thành phần liên thông
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}

// Hàm để hợp nhất hai gia đình
void unionFamilies(int x, int y) {
int rootX = find(x);
int rootY = find(y);

if (rootX != rootY) {
// Luôn gộp vào root của y
parent[rootX] = rootY;
size[rootY] += size[rootX];
}
}

int main() {
int N, M;
cin >> N >> M;

// Khởi tạo từng người là một gia đình riêng biệt
for (int i = 1; i <= N; i++) {
parent[i] = i;
}

// Đọc các mối quan hệ huyết thống và xây dựng gia đình
for (int i = 0; i < M; i++) {
int x, y;
cin >> x >> y;
unionFamilies(x, y);
}

// Đếm số gia đình và số lượng thành viên của từng gia đình
set happyFamilies; // Dùng để đếm những gia đình hạnh phúc

for (int i = 1; i <= N; i++) {
if (parent[i] == i) { // Nếu là chỉ số gốc
int familySize = size[i];
if (familySize < 2) continue; // Bỏ qua những gia đình chỉ có 1 người
if (find(familySize) == familySize) // Nếu kích thước không phải là số nguyên tố
{
happyFamilies.insert(i);
}
}
}

// Kết quả là số lượng gia đình hạnh phúc
cout << happyFamilies.size() << endl;

return 0;
}
```

Giải thích chi tiết:

1. Thuật toán:
- Sử dụng cấu trúc dữ liệu Union-Find (hay còn gọi là Disjoint Set Union - DSU) để quản lý các nhóm người có quan hệ huyết thống. Mỗi người bắt đầu là một gia đình riêng biệt.
- Khi có quan hệ huyết thống giữa hai người, chúng ta sử dụng hàm `unionFamilies` để hợp nhất hai gia đình thành một.

2. Tính số lượng thành viên trong mỗi gia đình:
- Mảng `size` lưu kích thước của từng gia đình và được cập nhật khi hợp nhất các gia đình.

3. Xác định gia đình hạnh phúc:
- Gia đình hạnh phúc là gia đình nào có số lượng người không phải là số nguyên tố. Để kiểm tra, ta có thể sử dụng một hàm kiểm tra số nguyên tố.

4. Đếm gia đình hạnh phúc:
- Sử dụng set để đếm số gia đình hạnh phúc một cách duy nhất.

5. Kết quả:
- Kết quả cuối cùng in ra số lượng gia đình hạnh phúc.

Mọi yếu tố của bài toán đều được xử lý một cách chặt chẽ và hiệu quả thông qua các cấu trúc dữ liệu và thuật toán phù hợp.

Đăng phản hồi