Ta có một cây gồm n đỉnh. Ta được phép chọn gốc tùy ý, và yêu cầu là tìm số lượng lá lớn nhất có thể trong cây đó.
**Định nghĩa:** Lá là đỉnh không có con nào nếu xét cây có gốc. Tương đương, trong đồ thị ban đầu, một đỉnh có bậc bằng 1 (nối với đúng một đỉnh khác) là một lá (ngoại trừ khi cây chỉ có một đỉnh).
---
**Dễ thấy**
- Nếu n = 1, thì cây chỉ có một đỉnh duy nhất. Khi đó, chính nó được xem là lá. Do đó, đáp án là 1.
- Nếu n = 2, thì cây gồm 2 đỉnh và 1 cạnh nối giữa chúng. Dù chọn gốc là đỉnh nào, đỉnh còn lại sẽ là lá. Đáp án vẫn là 1.
- Nếu n >= 3, thì mọi đỉnh có bậc bằng 1 đều có thể là lá nếu chọn gốc một cách hợp lý (ví dụ chọn gốc ở “trung tâm” của cây).
---
**Ý tưởng:**
Duyệt qua tất cả các đỉnh và đếm xem có bao nhiêu đỉnh có bậc bằng 1. Đó chính là số lượng lá lớn nhất mà cây có thể có nếu ta chọn gốc một cách tối ưu.
---
**Thuật toán:**
- Bước 1: Nhập vào số đỉnh n và n - 1 cạnh.
- Bước 2: Với mỗi đỉnh, đếm số cạnh kề để biết bậc của nó.
- Bước 3: Đếm số đỉnh có bậc bằng 1 và in ra kết quả.
---
**Độ phức tạp:** O(n), do mỗi đỉnh và cạnh được duyệt đúng một lần.
Code :
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 1e5 + 1;
vector<vector<int>> adj(MaxN);
int n;
int main() {
cin >> n;
if(n == 1) {
cout << 1;
exit(0);
} else if(n == 2){
cout << 1;
exit(0);
}
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (adj[i].size() == 1)
cnt++;
}
cout << cnt << '\n';
return 0;
}
blua
Created at
1 likes