Bài toán số cách nối k thành phần liên thông năm 2024

Question

BÀI TOÁN

Nội dung chính Show

Thành phần song liên thông
Thuật toán tìm thành phần song liên thông
Ý tưởng
Cài đặt

Viết chương trình đếm số thành phần liên thông của đồ thị vô hướng Anxn với:
- A[i,j] = 1 nếu có đường đi từ i đến j, A[i,j] = 0 nếu không có đường đi từ i đến j. - A[i,j] = A[j,i]. Dữ liệu vào: cho trong file Bai2.inp nội dung dữ liệu giống dữ liệu Bài Toán 2. Dữ liệu ra: hiển thị số thành phần liên thông của đồ thị ra màn hình. Ví dụ: BAI3.INP 6 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 MIEN LIEN THONG: 2
BAI3.INP 5 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 MIEN LIEN THONG: 1

HƯỚNG DẪN THUẬT TOÁN

Ý tưởng: Sử dụng thuật toán loang giống như bài toán 2. Bước 0: Khởi tạo số thành phần liên thông bằng 0. Bước 1: Xuất phát từ một đỉnh chưa được đánh dấu của đồ thị. Ta đánh dấu đỉnh xuất phát, tăng số thành phần liên thông lên 1 và chuyển sang bước 2. Bước 2: Từ một đỉnh i đã đánh dấu, ta đánh dấu tất cả các đỉnh j nếu A[i,j] = 1 và j chưa được đánh dấu và chuyển sang bước 3. Bước 3: Thực hiện bước 2 cho đến khi không còn thực hiện được nữa chuyển sang bước 4. Bước 4: Nếu số số đỉnh đánh dấu bằng n (mọi đỉnh đều được đánh dấu) kết thúc thuật toán và trả về số thành phần liên thông, ngược lại quay về bước 1. Chú ý: Nếu số thành phần liên thông bằng 1 đồ thị liên thông.

CHƯƠNG TRÌNH MẪU

Code:

/Hàm trả về số thành phần liên thông của đồ thị vô hướng / int TPLien_Thong(int **A, int n) { char*DanhDau = new char [n]; char ThanhCong; int Dem=0, i,j, MLT=0; for( i = 0; i<n; i++) //Khởi tạo mọi đỉnh chưa được đánh dấu DanhDau[i] = 0; do { j = 0; while(DanhDau[j]==1) //B1: Tìm 1 đỉnh chưa được đánh dấu j++; DanhDau[j] = 1; //Đánh dấu đỉnh tìm được Dem++; //Tăng số đỉnh được đánh dấu lên 1 MLT++; //Tăng miền liên thông lên 1 do { ThanhCong =0; //Giả sử không còn khả năng loang for(i = 0; i<n; i++) if(DanhDau[i]==1) for(j = 0; j<n; j++) if (DanhDau[j] == 0 && A[i][j] > 0) { DanhDau[j] = 1; ThanhCong =1; //Còn khả năng loang Dem++; if(Dem == n) return MLT; } }while (ThanhCong == 1); //Lặp khi còn khả năng loang } while(Dem<n); //Lặp khi còn tồn tại đỉnh chưa được dánh dấu return MLT; }

Như vậy, có thể hiểu một thành phần liên thông mạnh của một đồ thị có hướng là một đồ thị con tối đại liên thông mạnh (nghĩa là nếu thêm vào thành phần liên thông này một tập hợp đỉnh khác sẽ làm mất đi tính liên thông mạnh). Nếu mỗi thành phần liên thông mạnh được co lại thành một đỉnh, thì đồ thị sẽ trở thành một đồ thị có hướng không chu trình. Giải thuật Tarjan là một giải thuật rất được ưa thích để tìm các thành phần liên thông mạnh trên đồ thị.

Đồ thị vô hướng ~G(V, E)~ được gọi là liên thông (connected) nếu giữa mọi cặp đỉnh của ~G~ luôn tồn tại đường đi. Ví dụ hình dưới đây là một đồ thị liên thông.

Cho đồ thị vô hướng ~G = (V, E)~, ~U~ là một tập con của ~V~. Ta nói ~U~ là một thành phần liên thông của ~G~ nếu hạn chế của ~G~ trên tập ~U: G_U = (U, E_U)~ là một đồ thị liên thông. Ví dụ hình dưới đây là đồ thị có ~3~ thành phần liên thông.

Bài toán:Cho đơn đồ thị vô hướng ~G(V, E)~ có ~n~ đỉnh và ~m~ cạnh. Hãy tìm các thành phần liên thông của ~G~.

Input

Dòng đầu chứa hai số nguyên ~n~ và ~m~ là số đỉnh và số cạnh của đồ thị ~G~;
~m~ dòng tiếp theo, mỗi dòng chứa một cặp số ~u, v~ cho biết một cạnh liên thuộc giữa ~u~ và ~v~ trong ~G~.

Giới hạn:

~1 ≤ n ≤ 1000; 0 ≤ m ≤ \frac{n(n – 1)}{2}~.

Output

Dòng đầu ghi số nguyên dương ~C~ là số thành phần liên thông trong ~G~;
~C~ dòng tiếp theo, mỗi dòng ghi một thành phần liên thông theo khuôn dạng: Số ~v~ đầu là số đỉnh của thành phần liên thông, ~v~ số tiếp theo là danh sách các đỉnh "liệt kê theo thứ tự tăng dần".
Lưu ý: Không in ra các khoảng trắng dư thừa!

Hai số trên cùng một dòng được ghi cách nhau một dấu cách, "các thành phần liên thông liệt kê theo thứ tự các đỉnh nhỏ nhất tăng dần".

Xét đồ thị vô hướng, đỉnh khớp (cut vertex) là đỉnh mà nếu xóa đi sẽ làm tăng số thành phần liên thông.

Ví dụ trong đồ thị sau, các đỉnh đỏ là đỉnh khớp:

Một đồ thị vô hướng được gọi là song liên thông (biconnected) nếu nó liên thông và không có đỉnh khớp, nghĩa là nếu xóa một đỉnh bất kì thì đồ thị vẫn liên thông.

Thành phần song liên thông

Xét đồ thị vô hướng \(G\), thành phần song liên thông được định nghĩa là đồ thị con song liên thông cực đại của \(G\). Cụ thể hơn, \(G'\) là một thành phần song liên thông của \(G\) thì ta có:

\(G'\) là đồ thị con của \(G\).
\(G'\) song liên thông.
\(G'\) là cực đại (maximal), nghĩa là không thể thêm đỉnh vào \(G'\) mà vẫn giữ được tính song liên thông.

Ví dụ trong hình sau, các đỉnh cùng màu cùng chung một thành phần song liên thông:

Ta thấy một đỉnh có thể thuộc vào nhiều thành phần song liên thông khác nhau và các đỉnh thuộc nhiều thành phần song liên thông đều là khớp.

Thuật toán tìm thành phần song liên thông

Có nhiều cách để tìm thành phần song liên thông, cách phổ biến nhất là duyệt theo kiểu Tarjan. Tuy nhiên, phần sau sẽ trình bày cách dùng phương pháp nén đường (path compression) và cấu trúc disjoint-sets để tìm thành phần song liên thông.

Ý tưởng

Ta thấy các đỉnh cùng nằm trên một chu trình đơn sẽ cùng thuộc một thành phần song liên thông.

Ý tưởng của phương pháp nén đường là kết hợp việc DFS với tìm TP song liên thông, các đỉnh cùng thuộc một TP song liên thông sẽ được hợp nhất lại bằng disjoint-sets.

Cụ thể, khi đang duyệt đỉnh \(u\) và có cạnh nối ngược lên \(v\), ta thấy các đỉnh \((v, 2, 3, u)\) tạo nên một thành phần song liên thông, ta sẽ hợp nhất các đỉnh này lại. Mỗi TP sau khi hợp nhất được đại diện bởi đỉnh có bậc nhỏ nhất trên cây DFS.

Tuy nhiên, do đỉnh \(v\) có thể thuộc TP song liên thông khác nên ta chỉ hợp nhất từ đỉnh \(2\) đến đỉnh \(u\).

Cài đặt

Trong quá trình DFS ta sẽ quản lý một stack chứa các đỉnh đang được duyệt, với các đỉnh đã được hợp nhất thì chỉ lưu đỉnh có bậc nhỏ nhất. Ngoài ra ta cũng cần lưu đỉnh con đang được duyệt của mỗi đỉnh.

Code như sau:

// Danh sách kề
typedef vector<vector<int>> dsk;

# define N 30001

// Cấu trúc disjoint-sets
int root[N];
int find(int u) {
    if (root[u] != u) root[u] = find(root[u]);
    return root[u];
}
bool visited[N];
int active[N];
vector<int> stack;
void dfs(int u, const dsk &ke) {
    visited[u] = true;
    root[u] = u;
    stack.push_back(u);
    for (int v: ke[u]) if (visited[v]) {
        v = find(active[v]);
        while (stack.back() != v) {
            root[find(stack.back())] = v;
            stack.pop_back();
        }
    }
    for (int v: ke[u]) if (!visited[v]) {
        active[u] = v;
        dfs(v, ke);
    }
    if (stack.back() == u) stack.pop_back();
}

Sau khi DFS xong, mỗi tập hợp trong disjoint-sets là một TP song liên thông, cộng thêm 1 đỉnh là đỉnh cha của gốc TP song liên thông đó.

mẹo hay Mẹo Hay Cách