Author: admin

SÓ LƯỢNG THÀNH PHẦN LIÊN THÔNG -Có 10 test. Mỗi test 0.7 điểm -Đáp án: Để giải bài này, đơn giản là dựng danh sách kề cho đồ thị B, sau đó dùng DFS để tìm số lượng các thành phần liên thông và độ lớn của chúng. Bài 2 Tuy nhiên, phương pháp này sẽ làm tràn bộ nhớ, vì cho rằng N = M = 105 thì sẽ có NN-M cạnh trong đồ thị B. Cũng vì vậy, với N + M ≤ 2105 nhưng sẽ có N*(N-1)/2-M cạnh trong B, số lượng cạnh dễ dàng vượt quá 108, số lượng cạnh như vậy phương pháp DFS bình thường sẽ bị quá thời gian. Giải pháp 1: Dùng một tập hợp để lưu giữ cácđỉnhchưaviếngthăm. Với mỗi đỉnh từ 1 đến N, thực hiện DFS nếu nó chưa được viếng thăm, khi thực hiện DFS ta sẽ gỡ bỏ đỉnh này ra khỏi cácđỉnhchưaviếngthăm, trong hàm DFS ta sẽ dò trên cácđỉnhchưaviếngthăm còn lại bằng cách dùng hàm upperbound. Gọi u là đỉnh hiện tại của hàm DFS. Lặp lại trên cácđỉnhchưaviếngthăm, gọi đỉnh này là v. Với các đỉnh v đó, nếu có cạnh (uv) tồn tại trong A, ta sẽ viếng thăm v và gỡ nó ra khỏi cácđỉnhchưaviếng_thăm. Giải pháp 2: Chọn những đỉnh có bậc lớn hơn n/2 trong đồ thị B. Fact: Bất kỳ 2 đỉnh nào như trên đều nằm trong cùng một thành phần liên thông. Lý do: Với 2 đỉnh bất kỳ có bậc > n/2, sẽ tồn tại mộ đỉnh thứ 3 mà đỉnh này sẽ có cạnh nối đến 2 đỉnh kia. Với những đỉnh có bậc <= n/2, tạ có thể dùng phương pháp DFS bình thường hoặc DSU. Tổng bậc của tất cả các đỉnh đó tối đa là m, vì vậy áp dụng DFS bình thường trên các đỉnh đó sẽ không vượt quá thời gian quy định