// https://oj.luyencode.net/problem/LIBRARY
#include
using namespace std;
using ll = long long;
const int maxN = 100001;
int n, m; ll a[maxN];
vector adj[maxN];
bool visited[maxN];
ll res = 0;
int BFS(int src) {
ll val = a[src]; // set so tien xay thu vien tai tpho src
queue q;
q.push(src);
visited[src] = true;
while(!q.empty()) {
int u = q.front(); q.pop();
for(auto it: adj[u]) {
if(!visited[it]) {
val = min(val, a[it]); // cap nhat neu co thanh pho ma so tien nho hon
visited[it] = true;
q.push(it);
}
}
}
return val;
}
void solve() {
for(int i = 1; i <= n; i++) {
if(!visited[i]) {
//tim cac thanh pho lien thong, tra ve so tien nho nhat tai cac thanh pho do
res += BFS(i);
}
}
cout << res;
}
void input() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
visited[i] = false;
}
for(int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
input();
solve();
return 0;
}
Chi tiết bài tập - Luyện Code Online
https://oj.luyencode.net/problem/LIBRARY