Hướng dẫn giải của Sửa chữa đường xá
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Thuật toán
Đáp án = số thành phần liên thông ~- 1~.
Tính chất cơ bản của đồ thị: Số cạnh vô hướng ít nhất để một đồ thị ~n~ đỉnh liên thông sẽ là ~n-1~ cạnh. Hay nói cách khác, đó chính là số cạnh của một cây khung của đồ thị.
Trong bài này đồ thị có ~n~ đỉnh và ~m~ cạnh. Vì các đỉnh thuộc cùng một thành phần liên thông thì có thể đi lại được với nhau, nên ta chỉ cần thêm cạnh nối ~2~ đỉnh thuộc ~2~ thành phần liên thông khác nhau để tạo ra ~1~ thành phần liên thông mới. Như vậy ta sẽ cần ~k-1~ cạnh như vậy (với ~k~ là số thành phần liên thông của đồ thị) để đưa đồ thị về còn ~1~ thành phần liên thông duy nhất. Hay nói cách khác, ta có thể xem đồ thị ~G'~ mới có ~k~ đỉnh với mỗi đỉnh đại diện cho ~1~ thành phần liên thông của đồ thị ~G~ ban đầu, và từ đó suy ra cần thêm ít nhất ~k-1~ cạnh để chúng liên thông với nhau.
Xét test ví dụ: đồ thị gồm ~7~ đỉnh và ~5~ cạnh
Ta xác định được đồ thị gồm có ~3~ thành phần liên thông ~(1, 2, 3), (4, 7), (5, 6)~. Sau đó, ta có thể chọn ~2~ cạnh nối hai đỉnh thuộc ~2~ thành phần liên thông khác nhau. Chẳng hạn nối ~(2, 6), (3, 7)~ và có được đồ thị mới gồm ~1~ thành phần liên thông như sau:
Code tham khảo
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;
/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
bool maximize(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
/***End of Template***/
int n, m;
const int N = 2e5+4;
vi adj[N];
bool visited[N];
void Input() {
cin >> n >> m;
FOR(i, 1, m) {
int u, v; cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
}
void dfs(int u) {
visited[u] = true;
for(int v : adj[u]) if (!visited[v]) {
dfs(v);
}
}
void Solve() {
memset(visited, 0, sizeof visited);
int cnt = 0;
FOR(i, 1, n) if (!visited[i]) {
cnt++;
dfs(i);
}
cout << cnt-1;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
Input(), Solve();
return 0;
}
Bình luận