{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"Trong một đồ thị vô hướng có trọng số cạnh, cây khung nhỏ nhất là một tập hợp các cạnh có tổng trọng số nhỏ nhất sao cho bất kỳ hai nút nào cũng được kết nối bằng một đường đi chỉ chứa các cạnh này. Một thuật toán phổ biến để tìm cây khung nhỏ nhất T trong đồ thị là như sau:\n- Ban đầu, để T rỗng.\n- Xem xét các cạnh e-1,...,em theo thứ tự tăng dần của trọng số.\n— Thêm ei vào T nếu hai điểm cuối của ei không được kết nối bởi một đường đi trong T.\n\nMột thuật toán khác là như sau:\n- Ban đầu, để T là tập hợp tất cả các cạnh.\n- Trong khi có một số chu trình C trong T.\n— Loại bỏ cạnh e khỏi T nơi e có trọng số nặng nhất trong C.\n\nNhiệm vụ của bạn là thực hiện một hàm liên quan đến thuật toán này. Cho một đồ thị vô hướng G với trọng số cạnh, nhiệm vụ của bạn là xuất ra tất cả các cạnh là cạnh nặng nhất trong một số chu trình của G.\n\n### Đầu vào\nĐầu vào đầu tiên của mỗi trường hợp bắt đầu với số nguyên n và m với 1 \u003c n \u003c 1,000 và 0 \u003c m \u003c 25,000 nơi n là số lượng nút và m là số lượng cạnh trong đồ thị. Theo sau là m dòng chứa ba số nguyên u, v, và w mô tả một cạnh có trọng số w nối các nút u và v nơi 0 \u003c u, v \u003c n và 0 \u003c w \u003c 2^31. Đầu vào kết thúc với một dòng chứa n \u003d m \u003d 0; trường hợp này không được xử lý. Bạn có thể giả định không có hai cạnh nào có cùng trọng số và không có hai nút nào được kết nối trực tiếp bởi nhiều hơn một cạnh.\n\n### Đầu ra\nĐầu ra cho mỗi trường hợp đầu vào bao gồm một dòng chứa trọng số của tất cả các cạnh là cạnh nặng nhất trong một số chu trình của đồ thị đầu vào. Các trọng số này nên xuất hiện theo thứ tự tăng dần và các trọng số liên tiếp nên được tách bằng một khoảng trắng. Nếu đồ thị không có chu trình thì xuất ra văn bản ‘forest’ thay vì các số.\n\n### Ví dụ\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\n0 1 1\n1 2 2\n2 0 3\n4 5\n0 1 1\n1 2 2\n2 3 3\n3 1 4\n0 2 0\n3 1\n0 1 1\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\nforest\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}