SPOJ.COM - Thuật toán bài PT07Y - Is it a tree

Posted on September 23rd, 2016

Đề 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 

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 mình 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

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 mình 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 mình 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 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;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Xin chào và hẹn gặp lại, thân ái!