NYTRAVEL - Mạng lưới giao thông
Xem dạng PDF
Đất nước Free Contest đang trong quá trình xây dựng nên mạng lưới giao thông còn chưa hoàn thiện. Mạng lưới giao thông của đất nước này kết tối ~n~ thành phố bởi ~m~ con đường hai chiều.
Các thành số được đánh số từ ~1~ đến ~n~. Đội tình nguyện viên của Free Contest đang ở thành phố ~1~. Nhân dịp tết cổ truyền đang đến gần, đội tình nguyện viên muốn đi thăm nhiều thành phố nhất có thể. Nhưng vì mạng lưới giao thông chưa hoàn thiện, số thành phố các tình nguyện viên có thể thăm là khá ít. Họ quyết định xây thêm một con đường một chiều kết nối hai thành phốnào đó để tăng số lượng thành phố có thể đến thăm nhiều nhất có thể.
Tony nhận ra bài toán đếm số lượng tối đa thành phố có thể đến thăm sau khi xây dựng thêm một con đường rất thú vị, vì vậy anh ta quyết định đưa bài toán này vào contest sắp tới. Bạn sẽ giải quyết được bài toán này chứ?
Input
- Dòng đầu tiên chứa hai số nguyên dương ~n, m~ lần lượt là số lượng thành phố và số lượng con đường hai chiều trong mạng lưới giao thông ~(1 ≤ n, m ≤ 100000)~;
- ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~u, v~ miêu tả rằng có một đường hai chiều kết nối giữa hai thành phố ~u~ và ~v~ trong mạng lưới giao thông ~(u, v ≤ n)~.
Output
- Đưa ra một số nguyên duy nhất là số lượng thành phố tối đa đội tình nguyện viên có thể đến thăm.
Sample
Input #1
3 2
1 2
3 2
Output #1
3
Input #2
5 3
1 4
4 2
2 1
Output #2
4
Problem source: Kc97ble - Free Contest
Bình luận
Gợi ý: duyệt bfs(1); duyệt bfs(2->n); tìm ra tplt lớn nhất từ 2 -> n; đáp án là tplt (1) + tplt(2->n);
Gợi ý: n thành phố bởi m con đường 2 chiều tức là đồ thị n đỉnh m cạnh, 2 chiều tức là đồ thị vô hướng. Từ thành phố 1 muốn thăm nhiều thành phố nhất có thể tức là tìm cạnh nối sao cho số đỉnh của thành phần liên thông mà 1 thuộc về nhiều nhất có thể. Idea bài này sẽ là: Sử dụng DSU để tìm số phần tử của mỗi thành phần liên thông trong đồ thị. Nếu đồ thị đã liên thông, số đỉnh tối đa thăm được sẽ là cả n đỉnh. Ngược lại, ta nhận thấy rằng từ 1 sẽ đi được hết các đỉnh cùng TPLT với 1. Và đương nhiên, nối 2 thành phần liên thông với nhau thì ta chỉ cần nối 1 đỉnh tập này và 1 đỉnh tập kia mà thôi. Do đó, trong trường hợp đồ thị không liên thông, ta sẽ nối TPLT nhiều phần tử nhất với TPLT mà 1 thuộc về
cho mik xin case test 1 dc ko aj