Editorial for Thi thử Duyên hải 2021 - Lần 1 - Bài 2 - EDGE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: SPyofgame


~\color{green}{\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{orange}{\text{Hướng dẫn}}~

  • Chúng ta ~dfs(u)~ để tìm cầu tại ~u~ (nếu có), đồng thời để tiện ta có thể tính luôn số đỉnh nằm ở trong cây con gốc ~u~

  • 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


~\color{goldenrod}{\text{Tiếp cận}}~

  • 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~
  • Xét các trường hợp

Đồ thị có hơn 2 thành phần liên thông, kết quả là ~res = 0~

Đồ thị có đúng 2 thành phần liên thống, kết quả là ~res = |L| \times |R| \times (m - |B|)~

  • Với ~|L|~ là số đỉnh thuộc thành phần thứ nhất
  • Với ~|R|~ là số đỉnh thuộc thành phần thứ hai
  • Với ~m~ là số cạnh có trong toàn bộ đồ thị
  • Với ~|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, kết quả là ~res = (\frac{n(n+1)}{2} - m) \times (m - |B|) + \underset{f \in B}{\Sigma}(f \times (n - f) - 1)~

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

~\color{purple}{\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{green}{\text{Code tham khảo }}~: Đồ thị, dfs, Tarjan

~^{^{\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 
*/

Comments

Please read the guidelines before commenting.


There are no comments at the moment.