SPOJ.COM - Thuật toán bài PT07Y - Is it a tree
Đề bài:
Bạn được cho một đồ thị không trọng số, và vô hướng. Viết chương trình để kiểm tra xem nó có phải là cây hay không.
Đầu vào:
Dòng đầu tiên của đầu vào sẽ bao gồm 2 số nguyên N và M, tương ứng là số lượng các điểm và số lượng cạnh trên đồ thị, với 0 < N <= 10000, 0 <= M <= 20000. Tiếp theo là M dòng chứa thông tin M cạnh của đồ thị. Mỗi dòng bao gồm một cặp u,v, nghĩa là có 1 cạnh giữa 2 điểm u, v với 1 <= u,v <= N.
Đầu ra:
In ra "YES" nếu như đồ thị đó là cây, ngược lại in ra "NO".
Ví dụ:
Đầu vào:
3 2
1 2
2 3
Đầu ra:
YES
Các bạn có thể tham khảo đề bài tiếng anh và submit code tại: http://www.spoj.com/problems/PT07Y/
Phân tích:
- Trước tiên, để giải được bài toán này, bạn phải hiểu thế nào là cây. Theo tôi hiểu một cách đơn giản là: cây là một đồ thị liên thông, và không có chu trình nào. Do đó, nếu cây có N đỉnh thì sẽ có đúng N-1 cạnh. + Ta sẽ dùng thuật toán tìm kiếm theo chiều sâu DFS để duyệt đồ thị.
Lời giải:
(Các 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 tôi 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 tôi 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 các bạn.)
Code C/C++:
| #include<iostream> | |
| using namespace std; | |
| const int MAX = 10005; | |
| int Matrix[MAX][MAX]; // Ma trận lưu trạng thái của đồ thị | |
| bool Visit[MAX]; // Mảng đánh dấu mỗi điểm được thăm hay chưa | |
| int cnt; // Đếm số điểm đi qua trong 1 lần duyệt để biết | |
| // đồ thị có liên thông hay không | |
| int N, M; // Lần lượt là số đỉnh và số cạnh | |
| void Try(int u) | |
| { | |
| Visit[u] = 1; | |
| cnt++; | |
| for (int i = 1; i <= Matrix[u][0]; i++) | |
| { | |
| int v = Matrix[u][i]; | |
| if(!Visit[v]) Try(v); | |
| } | |
| } | |
| int main() | |
| { | |
| ios::sync_with_stdio(false); | |
| // Comment dòng này trước khi submit | |
| freopen("input.txt","r",stdin); | |
| cin >> N >> M; | |
| if(M == 0) cout << "NO" << endl; | |
| else | |
| { | |
| cnt = 0; | |
| for(int i = 0; i <= N; i++) | |
| { | |
| Visit[i] = false; | |
| for(int j = 0; j <= N; j++) | |
| Matrix[i][j] = 0; | |
| } | |
| // Tại hàng thứ i trong ma trận, | |
| // ta sẽ lưu id của những đỉnh kề với đỉnh i | |
| // Matrix[i][0] lưu số lượng đỉnh kề. | |
| for(int i = 0; i < M; i++) | |
| { | |
| int a, b, m; | |
| cin >> a >> b; | |
| m = ++Matrix[a][0]; | |
| Matrix[a][m] = b; | |
| m = ++Matrix[b][0]; | |
| Matrix[b][m] = a; | |
| } | |
| // Nếu số cạnh < số đỉnh trừ 1 thì chắc chắn không phải là cây | |
| if(M == N-1) | |
| { | |
| // Thử duyệt tại một điểm bất kì, ở đây là điểm 1 | |
| Try(1); | |
| // Khi số cạnh là N - 1 và đi được qua hết N điểm | |
| // thì chứng tỏ đồ thị liên thông. | |
| // và không có chu trình. Nên sẽ là cây. | |
| if(cnt == N) cout << "YES" << endl; | |
| else cout << "NO" << endl; | |
| } | |
| else cout << "NO" << endl; | |
| } | |
| return 0; | |
| } |
Code by Phạm Văn Lâm