let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI 2015 REFORM - Kế hoạch cải tổ

solution.md

Đề trên SPOJ bị thiếu, bài này có giới hạn \(n \leq 10^5, m \leq 2\times10^5\).

Ta có thể phát biểu bài toán dưới dạng đồ thị như sau:

Cho Một đồ thị vô hướng với n đỉnh và m cạnh, mục tiêu của ta là đếm số cách khác nhau để thực hiện 2 bước sau:

  • Loại bỏ một cạnh trong m cạnh của đồ thị
  • Thêm một cạnh mới vào đồ thị (cạnh này phải khác m cạnh lúc đầu) sao cho đồ thị mới đảm bảo tính liên thông.

Ta có nhận xét là do chỉ có thể thêm một cạnh vào đồ thị, do đó số lượng thành phần liên thông của đồ thị chỉ có thể tối đa là 2. Ta sẽ chia bài toán làm 2 trường hợp: Đồ thị gồm 1 thành phần liên thông và đồ thị gồm 2 thành phần liên thông.

Trường hợp thứ nhất - trường hợp đơn giản hơn: Đồ thị gồm 2 thành phần liên thông

Giả sử 2 thành phần liên thông của đồ thị có số đỉnh lần lượt là C1 và C2 (tất nhiên C1 = n - C2). Do đồ thị có 2 thành phần liên thông, cạnh ta thêm vào phải là cạnh từ thành phần liên thông này sang thành phần liên thông kia, có nghĩa là có C1 * C2 cách thêm cạnh, và các cạnh này chắc chắn khác với m cạnh lúc đầu. Tuy nhiên ta có thêm nhận xét là cạnh bị loại đi không được phép là cầu. Từ đó, giả sử số cầu của đồ thị là c, kết quả của ta là (m-c) * C1 * C2.

Trường hợp thứ hai: Đồ thị có duy nhất một thành phần liên thông

Cố định cạnh bỏ đi (xét từng cạnh trong m cạnh của đồ t), ta sẽ chia bài toán làm 2 trường hợp:

Trường hợp đầu tiên: cạnh bỏ đi không phải là cầu, khi đó đồ thị vẫn tiếp tục liên thông. Tức là ta có thể thêm bất cứ cạnh nào miễn sau cạnh đó khác m cạnh lúc đầu là được, như vậy lúc này ta có \(n(n-1) / 2 - m\) cách thêm cạnh mới.

Trường hợp thứ hai: cạnh bỏ đi là cầu, khi đó đồ thị sẽ bị chia làm 2 thành phần liên thông, và cạnh thêm vào chắc chắn phải nối một đỉnh từ thành phần liên thông này sang đỉnh thuộc thành phần liên thông kia (để đảm bảo tính chất liên thông của đồ thị). Gọi C1 và C2 là số lượng đỉnh trong 2 thành phần liên thông sau khi bỏ đi cạnh đang xét, ta sẽ có C1 * C2 - 1 cách thêm cạnh mới vào (-1 do trong C1 * C2 cạnh thì có một cạnh trùng với cạnh vừa bỏ đi).

Lấy tổng số cách trong các trường hợp, ta thu được kết quả của bài toán.

Độ phức tạp: O(m + n)

Nguồn: Tạp chí tin học và nhà trường

main.cpp
Open in Github • Download 
#include <cstdio>
#include <vector>
using namespace std;
#define LL long long

int n, m;
vector<int> ke[100000];

void dfs(int u, vector<bool> &visited) {
    visited[u] = true;
    for (int v: ke[u]) if (!visited[v]) dfs(v, visited);
}

int count_ccs() {
    int c = 0;
    vector<bool> v(n, false);
    for (int i=0; i<n; i++) if (!v[i]) dfs(i, v), c++;
    return c;
}

int dfs1(int i, vector<int>& idx, vector<int> &low, vector<int> &trace, int &index, LL &res, int &nBridge) {
    int nChild = 0;
    index += 1;
    idx[i] = low[i] = index;
    for (int j: ke[i]) {
        if (!idx[j]) {
            trace[j] = i;
            int nChildJ = dfs1(j, idx, low, trace, index, res, nBridge);
            nChild += nChildJ;
            low[i] = min(low[i], low[j]);
            if (low[j] > idx[i]) {
                nBridge++;
                res += (LL)nChildJ * (LL)(n-nChildJ) - 1ll;
            }
        } else if (j != trace[i]) low[i] = min(low[i], idx[j]);
    }
    return nChild + 1;
}

void solve1() {
    int index = 0, nBridge = 0;
    LL res = 0;
    vector<int> idx(n, 0), low(n, 0), trace(n, 0);
    dfs1(0, idx, low, trace, index, res, nBridge);
    res += (LL)(m-nBridge) * ((LL)n * (LL)(n-1) / 2ll - (LL)m);
    printf("%lld", res);
}

void dfs2(int i, vector<int>& idx, vector<int> &low, vector<int> &trace, int &index, int &num_bridge) {
    index += 1;
    idx[i] = low[i] = index;
    for (int j: ke[i]) {
        if (!idx[j]) {
            trace[j] = i;
            dfs2(j, idx, low, trace, index, num_bridge);
            low[i] = min(low[i], low[j]);
            if (low[j] > idx[i]) num_bridge++;
        } else if (j != trace[i]) low[i] = min(low[i], idx[j]);
    }
}

void solve2() {
    int index = 0, nBridge = 0;
    vector<int> idx(n, 0), low(n, 0), trace(n, 0);
    dfs2(0, idx, low, trace, index, nBridge);
    int c1 = index;
    for (int i=0; i<n; i++) if (!idx[i]) {
        dfs2(i, idx, low, trace, index, nBridge);
        break;
    }
    LL res = (LL)(m-nBridge) * (LL)c1 * (LL)(n-c1);
    printf("%lld", res);
}


int main() {
    scanf("%d%d", &n, &m);
    for (int i=0; i<m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }

    int num_ccs = count_ccs();
    if (num_ccs > 2) printf("0");
    else if (num_ccs == 2) solve2();
    else solve1();
    return 0;
}
Comments