Hướng dẫn giải của Thi thử Duyên hải 2021 - Lần 1 - Bài 2 - EDGE
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
~\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
*/
Bình luận