CEDGE
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một cây (đồ thi liên thông vô hướng không chu trình) gồm \(N\) nút. Các nút được đánh số từ 1 đến \(N\).
Nhiệm vụ của bạn là tô màu các cạnh trên cây, sao cho với mỗi nút, không có hai cạnh bất kì kề với nút đó được tô cùng một màu. Trong các cách tô màu thỏa mãn, hãy tìm cách tô dùng ít màu phân biệt nhất.
Lưu ý: Nếu có nhiều cách tô dùng ít màu phân biệt nhất và thỏa mãn điều kiện, bạn có thể in ra một cách bất kì.
Input
- Dòng đầu tiên gồm một số nguyên \(N (2<N<10^5)\).
- \(N—1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\) \((1<a_i,b_i<N)\) biểu diễn cạnh nối giữa nút \(a_i\) và \(b_i\).
Output
- Dòng đầu tiên in ra một số nguyên \(K\) là số lượng màu phân biệt ít nhất được dùng để tô.
- \(N—1\) dòng tiếp theo, dòng thứ \(i\) in ra một số nguyên \(c_i\) \((1<c_i<K)\) biểu diễn màu của cạnh thứ \(i\) trong cách cho ban đầu.
Example
Test 1
Input
3
1 2
2 3 Output
2
1
2Test 2
Input
8
1 2
2 3
2 4
2 5
4 7
5 6
6 8 Output
4
1
2
3
4
1
1
2Test 3
Input
6
1 2
1 3
1 4
1 5
1 6 Output
5
1
2
3
4
5
Bình luận
Bài này hình như test lỗi thì phải thấy in cái j cũng ac
Mình xin chia sẻ lời giải bài này như sau:
Gọi \(Edges[i]\) là vector chứa tất cả các đỉnh kề với đỉnh \(i\).
Khi đó ta có : Số màu tối thiểu cần dùng để thoả mãn yêu cầu bài toán chính với \(Max(Edges[i].size())\) với \(i=1,2,...,n\).
Và ta sẽ đi chứng minh điều này như sau:
Khi đó việc chứng minh sẽ gồm \(2\) phần sau:
Ta sẽ chứng minh những giá trị nhỏ hơn \(f\) sẽ không thoả mãn yêu cầu bài toán \(\implies\) Điều này rõ ràng vì nếu ta dùng \(t\) màu để tô với \(t\) nhỏ hơn \(f\) thì khi đó tồn tại đỉnh \(j\) với \(f=Edges[j].size()\) sẽ không thoả mãn yêu cầu bài toán.
Ta sẽ chứng minh, với \(f\) màu, ta sẽ tồn tại một cách tô thoả mãn yêu cầu bài toán, cụ thể ta tô như sau:
Gọi bốn màu ta cần tô là màu \(1,2,3,4\).
Khi đó ta tô như sau:
Khi đó ta sẽ tô màu tất cả các đỉnh còn lại trong \(edges[i]\) theo quy luật sau: \((k+1)\text{ mod }f+1,(k+2)\text{ mod }f+1,...\) cho đến hết các đỉnh \(edges[i]\). Vì số lượng màu tối đa ta có thể dùng trong một tập \(edges[i]\) là \(f\), nên rõ ràng với cách tô như vậy, những đỉnh được tô mà kề với \(i\) sẽ khác nhau từng đôi một. (Để hiểu rõ hơn, các bạn có thể xem mình minh hoạ).
Như vậy là ý tưởng tô màu đã hoàn thiện.
Việc còn lại chỉ là code.
Thì ở đây, mình sử dụng bfs để tô màu các đỉnh kết hợp với mảng points_edges[]. Mảng này có tác dụng lưu lại màu \(k\) của đỉnh \(j\) đã được tô trong tập đỉnh \(edges[i]\)
Cụ thể các bạn có thể xem code tại đây
Như vậy là bài toán đã được giải quyết, nếu có gì không hiểu các bạn comment nhé !