\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.99}}}}}\)

\(\color{#008b8b}{\text{Đọc hiểu đề}}\)

• Cho trước đồ thị vô hướng không trọng số gồm \(n\) đỉnh và \(m\) cạnh \((u, v)\)

• Hỏi số cách để xóa một cạnh \((u, v)\) đã có và thêm một cạnh \((u, v)\) chưa có (không xóa và thêm cùng một cạnh) sao cho bất kì 2 điểm \(u, v\) bất kì trong đồ thị cũng đến được nhau là bao nhiêu

\(\color{#008b8b}{\text{Hướng dẫn trâu}}\)

• Với mỗi cạnh bị xóa đi, ta thử duyệt qua các cạnh còn thiếu để xây thêm (không bao gồm cạnh bị phá hủy). Sau đó ta thử duyệt các cặp đỉnh xem từ có tồn tại đường đi từ \(u \rightarrow v\) hay không, nếu tất cả đỉnh \(u\) đều thỏa thì tăng biến đếm

• Tối ưu hơn: Sau khi xóa và thêm cạnh, ta chỉ cần kiểm tra xem đỉnh \(u\) có đi qua được tất cả các đỉnh còn lại không. Vì nếu tồn tại một đường đi như thế, thì mọi đỉnh trong đường đi đó đều đi đến được với nhau

\(\color{#008b8b}{\text{Tiếp cận trâu}}\)

• Gọi tập \(G_u\) là các đỉnh kề với \(u\)

• Gọi tập \(S\) là tập những cạnh mà đã có. Ban đầu khởi tạo rỗng.

• Gọi tập \(T\) là tập những cạnh mà chưa có. Ban đầu khởi tạo chứa mọi cặp cạnh \(u-v\) với \(1 \leq u, v \leq n\).

• Sau đó với mỗi cặp cạnh \(u-v\) được thêm vào tập thì ta xóa đi cạnh \(u-v\) khỏi \(T\) và thêm vào tập \(S\)

• Khởi tạo biến đếm kết quả là \(res = 0\)

• Thử duyệt qua các cạnh \(u_S-v_S\) đã có trong đồ thị để xóa (thuộc tập cạnh \(S\)). Rồi duyệt qua cạnh cạnh \(u_T-v_T\) chưa có trong đồ thị đê thêm (thuộc tập cạnh \(T\)). Rồi ta chạy dfs từ đỉnh bất kì

Xét việc \(dfs(u, p)\) từ đỉnh \(u\) và cha là \(p\) (ban đầu \(p\) là giá trị đặc biệt mà không đỉnh nào tới được)

Nếu đỉnh đã được thăm thì bỏ qua, ngược lại đánh dấu đã thăm

Nếu \(u = u_T\) thì ta gọi thêm \(dfs(v_T, u)\)

Nếu \(u = v_T\) thì ta gọi thêm \(dfs(u_T, u)\)

Duyệt qua các đỉnh kề \((v \in G_u \land v \neq p)\) nếu cạnh \(u-v\) không phải \(u_S - v_S\) (hay \(v_S - u_S\)) thì ta \(dfs(v, u)\)

Nếu mọi đỉnh đều được thăm thì tăng biến đếm \(res = res + 1\)

\(\color{#008b8b}{\text{Độ phức tạp trâu}}\)

• Duyệt qua tập \(S\) mất \(O(|S|) = O(E) = O(V^2)\) (Nhân thêm \(log(|S|)\) nếu sài CTDL cây)

• Rồi duyệt tập \(T\) mất \(O(|T|) = O(V^2 + E)\) (Nhân thêm \(log(|T|)\) nếu sài CTDL cây)

• và \(dfs()\) toàn bộ các đỉnh, mỗi đỉnh không duyệt nhiều lần mất \(O(V)\)

• Vậy tổng độ phức tạp là \(O(V^5)\)

\(\color{#008b8b}{\text{Code tham khảo }}\): Trâu, dfs

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n^5 + m)\ \color{purple}{\text{thời gian}}\ ||\ O(n^2)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int LIM = 101;

int n, m;
vector<int> G[LIM];
bool S[LIM][LIM];
bool T[LIM][LIM];

int cnt = 0;
bool used[LIM];
int us, ut, vs, vt;
void dfs(int u, int p = -1)
{
    if (used[u]) return ;
    used[u] = true;
    ++cnt;

    if (u == ut) dfs(vt, u);
    if (u == vt) dfs(ut, u);
    for (int v : G[u])
    {
        if (u == us && v == vs) continue;
        if (u == vs && v == us) continue;
        if (v == p) continue;
        dfs(v, u);
    }
}

bool check()
{
    memset(used, false, sizeof(used));
    cnt = 0;
    dfs(1);

    return cnt == n;
}

int main()
{
    memset(S, false, sizeof(S));
    memset(T, true, sizeof(T));

    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;

        S[u][v] = S[v][u] = true;
        T[u][v] = T[v][u] = false;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int res = 0;
    for (us = 1; us <= n; ++us)
        for (vs = us + 1; vs <= n; ++vs)
            if (S[us][vs])
                for (ut = 1; ut <= n; ++ut)
                    for (vt = ut + 1; vt <= n; ++vt)
                        if (T[ut][vt])
                            if (check())
                                ++res;

    cout << res;
    return 0;
}

\(\color{#008b8b}{\text{Hướng dẫn tổ hợp}}\)

• Thay vì thử duyệt từng cạnh để xóa và để thêm, ta sẽ sử dụng tổ hợp, dựa trên thành phần liên thông của đồ thị và câu của đồ thị

Nhìn bài toán từ góc độ khác, thêm hoặc xóa những cạnh không thay đổi tới khả năng đi lại giữa mọi cặp đỉnh thì có số lần tăng biến đếm là như nhau. Nên gộp lại thành tổ hợp thì không cần duyệt toàn bộ trường hợp

Nếu số thành phần liên thông là 2 trở lên thì tồn tại đỉnh thuộc thành phần này va đỉnh thuộc thành phần khác không đi đến nhau

Nếu thêm hay xóa cầu thì số lượng thành phần liên thông sẽ tăng hay giảm

• TH1: Nếu đếm trong đồ thị có hơn 2 thành phần liên thông:

Dù xóa bất kì cạnh của đồ thị con nào, và thêm 1 cạnh để nối 2 đồ thị với nhau, thì vẫn còn vài đồ thị không liên kết với nhau.

Hay nói cách khác là tồn tại 2 đỉnh thuộc 2 đồ thị bất kì không đến được với nhau dù có làm cách nào

• TH2: Nếu đếm trong đồ thị có đúng 2 thành phần liên thông:

Ta không được xóa cầu, vì nó sẽ tạo ra 3 đồ thị con và sẽ tồn tại 2 đỉnh không đến được với nhau.

Ta không được nối 2 đỉnh cùng đồ thị với nhau vì 2 đỉnh thuộc đồ thị khác nhau không đến được với nhau

• TH3: Nếu đếm trong đồ thị có đúng 1 thành phần liên thông

Nếu xóa cạnh là cầu, thì đồ thị bị chia làm 2 phần, ta sẽ nối bất kì đỉnh của một bên cầu với đỉnh của bên cầu còn lại

Nếu xóa cạnh thường, thì ta sẽ thêm vào bất cứ cạnh nào cũng được, trừ những cạnh đã thêm và mới được xóa

• Để đếm số thành phần liên thông, tìm cầu trong đồ thị hay số đỉnh của mỗi thành phần sau khi xóa cầu ta có thể sài thuật toán Tarjan

\(\color{#008b8b}{\text{Tiếp cận tổ hợp}}\)

• Tại \(dfs(u)\), ta xét các đỉnh \(v\) kề \(u\) (hay \(v \in G_u\)) như sau:

Ta đánh dấu đỉnh \(u\) đã thăm

Ghi lại thời gian thăm tới đỉnh \(u\)

Số đỉnh trong cây con gốc \(u\) hiện giờ là \(1\)

Nếu \(v\) đã được thăm, thì cập nhật thời gian sớm nhất gặp một đỉnh trong cây con gốc \(u\)

Nếu \(v\) chưa được thăm

• Ta \(dfs(v)\) để xét cây con gốc \(v\) trước

• Só đỉnh trong cây con gốc \(u\) cộng thêm số đỉnh trong cây con gốc \(v\)

• Cập nhật lại thời gian nhỏ nhất gặp một đỉnh trong cây con gốc \(u\)

• Nếu thời gian nhỏ nhất gặp một đỉnh trong cây con gốc \(v\) lớn hơn thời gian xuất hiện đỉnh \(u\), thì rõ ràng cạnh \(u - v\) là câu

• Nếu \(u - v\) là cầu thì ta thêm cầu vào trong \(map\) đông thời để tiện tính toán, ta gán nó bằng số đỉnh trong cây con gốc \(v\)

• Đồ thị có hơn 2 thành phần liên thông:

Số cách thêm xóa là \(0\) vì luôn tồn tại cặp đỉnh không đến được nhau

• Đồ thị có đúng 2 thành phần liên thống:

Số cách thêm xóa là \(|L| \times |R| \times (m - |B|)\)

• \(|L|\) là số đỉnh thuộc thành phần thứ nhất
• \(|R|\) là số đỉnh thuộc thành phần thứ hai
• \(m\) là số cạnh có trong toàn bộ đồ thị
• \(|B|\) là số cầu có trong toàn đồ thị
• \(|L| \times |R|\) đại diện cho số cách thêm để nối 2 thành phần liên thông
• \(m - |B|\) đại diện cho số cách xóa không tăng thêm thành phần liên thông

• Đồ thị chỉ có 1 thành phần liên thông:

Số cách thêm xóa là \((\frac{n(n-1)}{2} - m) \times (m - |B|) + \underset{f \in B}{\Sigma}(f \times (n - f) - 1)\)

• \(n\) là số đỉnh có trong toàn bộ đồ thị
• \(m\) là số cạnh có trong toàn bộ đồ thị
• \((\frac{n(n-1)}{2} - m)\) là số cạnh có thể thêm được
• \((m - |B|)\) là số cách xóa cạnh không phải cầu
• \(f\) và \((n - f)\) là số đỉnh ở hai bên của cầu (mỗi cái chỉ bao gồm một đầu mút của cầu)
• \(\underset{f \in B}{\Sigma}(f \times (n - f) - 1)\) là xóa cầu hiện có và xây thêm cầu mới

\(\color{#008b8b}{\text{Độ phức tạp}}\)

• Việc dùng thuật toán tarjan để dfs chỉ mất \(O(n + m)\)

• Việc tính toán cũng chỉ xét trường hợp và cùng lắm duyệt mất \(O(m)\)

• Vậy độ phức tạp bài toán cả về thời gian lẫn bộ nhớ là \(O(n + m)\)

\(\color{#008b8b}{\text{Code tham khảo }}\): Đồ thị, Tarjan, Tổ hợp

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(n + m)\ \color{purple}{\text{thời gian}}\ ||\ O(n + m)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <map>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

typedef long long ll;
const int LIM = 2e5 + 25;

struct Edge 
{
    int u, v;
    Edge (int u = 0, int v = 0)
    : u(u), v(v) {}

    bool operator < (const Edge &o) const
    {
        return (u != o.u) ? (u < o.u) : (v < o.v);
    }
};

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

/// Graph main property
int n, m;
Edge E[LIM];
vector<int> G[LIM];

/// Construct Graph
void input()
{
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        E[i] = Edge(u, v);
    }
}

/// Bridge & Component property
int component = 0; /// number of components
int timer = 0;     /// clock of discovery time
bool used[LIM];    /// if node is used
int cap[10];       /// capacity of components
int dt[LIM];       /// discovery time
int mdt[LIM];      /// minimum discovery time
int cnt[LIM];      /// cnt of subtree
vector<int> B;     /// number of nodes in one part of anyside of this bridge

/// Tarjan Algorithm
void tarjan(int u, int p = -1)
{
    /// Init new property
    used[u] = true;
    cnt[u] = 1;
    dt[u] = mdt[u] = ++timer;
    ++cap[component];

    for (int v : G[u]) if (v != p)
    {
        if (used[v])
        {
            minimize(mdt[u], dt[v]);
        }
        else 
        {
            tarjan(v, u);
            cnt[u] += cnt[v];
            minimize(mdt[u], mdt[v]);
            if (mdt[v] > dt[u]) /// Bridge detected
            {
                B.push_back(cnt[v]);
            }
        }
    }
}

/// Solving function
void solve()
{
    memset(used, false, sizeof(used));
    cap[1] = cap[2] = 0;

    /// Precalculation: Flood-fill all graph
    for (int u = 1; u <= n; ++u)
    {
        if (!used[u])
        {
            /// No matter how you use your one link
            /// You cant make all components linked
            if (++component > 2) 
            {
                cout << 0;
                return ;
            }

            tarjan(u);
        }
    }

    if (component == 1)
    {
        /// Connect any pair of nodes but not over constructed edges
        ll res = (1LL * n * (n - 1) / 2 - m) * (m - B.size());

        /// Connect left part with right part in two sides of the bridge
        for (int f : B) res += 1LL * f * (n - f) - 1;   

        /// Output
        cout << res << '\n';
    }
    else /// (component == 2) 
    {
        /// Connect any pair of nodes in two components, but not the bridges
        cout << 1LL * cap[1] * cap[2] * (m - B.size()) << '\n';
    }

}

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    input();
    solve();
    return 0;
}

/*
25 34
1 2
1 3
2 3
2 5
2 6
3 4
3 6
4 8
4 9
5 7
7 10
7 11
7 20
10 11
10 12
11 12
9 13
9 17
9 18
13 14
13 15
13 18
14 15
16 18
16 17
17 18
18 19
19 22
19 23
21 23
21 22
22 23
23 24
20 25


1----------2----------6         12
 \         |\        /         / |
  \        | \      /         /  |
   \       |  \    /         /   |
    \      |   \  /         /    |
     \     |    \/         10---11           25
8     \    |    /\          \    |           |
|      \   |   /  \          \   |           |
|       \  |  /    \          \  |           |
|        \ | /      \          \ |           |
|         \|/        \          \|           |
4----------3          5----------7----------20
|               15
|              /  \                 22--------21
|             /    \               / |       /
|            /      \             /  |      /
9----------13--------14          /   |     /
|\        /                     /    |    /
| \      /                     /     |   /
|  \    /                     /      |  /
|   \  /                     /       | /
17---18--------------------19--------23-------24
|    /
|   /
|  /
| /
16

Bridge:  4 ---->  8  >>   1  nodes 
Bridge: 23 ----> 24  >>   1  nodes 
Bridge: 18 ----> 19  >>   5  nodes 
Bridge:  4 ---->  9  >>  12  nodes 
Bridge:  3 ---->  4  >>  14  nodes 
Bridge: 20 ----> 25  >>   1  nodes 
Bridge:  7 ----> 20  >>   2  nodes 
Bridge:  5 ---->  7  >>   6  nodes 
Bridge:  2 ---->  5  >>   7  nodes 
*/