Bài C - Educational Codeforces Round 33 (Div.2)

Bài C:
Đề bài: Vova tự hứa với bản thân rằng anh ấy sẽ không bao giờ chơi game nữa. Nhưng gần đây, Firestorm- một công ty phát triển game nôi tiếng - đã cho ra mắt một game mới, đó là World of Farcraft, và nó trở nên thật sự phổ biến. Dĩ nhiên, Vova bắt đầu chơi nó.
  Bây giờ, anh ấy đang cố gắng giải quyết một nhiệm vụ (quest). Nhiệm vụ này đi đến một khu dân cư (settlement) có tên là Overcity và lan truyền tin đồn cho khu dân cư đó.
 Vova biết rằng có n người trong đó. Một vài người là bạn của nhau, và họ chia sẻ thông tin cho nhau, ngoài ra Vova cũng biết rằng anh ấy có thể mua chuộc (bribe) một người để anh ấy hoặc cô ấy bắt đầu lan tin đồn; người thứ i muốn c(i) lượng vàng trong cuộc trao đổi để lan truyền tin đồn. Khi một người đã nghe được tin đồn, anh ta sẽ nói cho tất cả bạn của mình, và họ bắt đầu lan truyền tin đồn cho bạn của họ (miễn phí), và tương tự.

Nhiệm vụ được hoàn thành khi n người đều biết tin đồn. Tìm số vàng ít nhất Vova cần để hoàn thành nhiệm vụ?
 Hãy nhìn vào chú thích nếu bạn chưa hiểu vấn đề hoàn toàn.
Đầu vào:
+  Dòng đầu tiên chứa hai số nguyên n và m (1<=n<=10^5,0<=m<=10^5), lần lượt là số người trong khu dân cư và số cặp bạn.
+ Dòng thứ hai chứa n số nguyên c(i) (0<=c(i)<=10^9) - lượng vàng của người thứ i để truyền tin đồn.
+ m dòng tiếp theo chứa một cặp số nguyên (x(i),y(i)) đại diện cho x(i) và y(i) là bạn của nhau (1<=x(i),y(i)<=n,x(i)#y(i)).
Đảm bảo rằng, mỗi cặp được liệt kê nhiều nhất 1 lần.
Đầu ra:
In ra 1 số - là số lượng vàng tối thiểu cần tìm.
Ví dụ:
Đầu vào:
5 2
2 5 3 4 8
1 4
4 5
Đầu ra:
10
/***/
Đầu vào:
10 0
1 2 3 4 5 6 7 8 9 10
Đầu ra:
55
/**/
Đầu vào:
10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10
Đầu ra:
15
/***/
Chú thích:
Ở ví dụ đầu tiên quyết định tốt nhất là mua chuộc người đầu tiên (anh ấy sẽ lan truyền tin đồn đến người thứ tư, và người thứ tư sẽ lan truyền đến người thứ 5). Vova cũng sẽ phải mua chuộc người thứ hai và người thứ ba, vì vậy tất cả họ đều biết tin đồn.
Ở ví dụ thứ 2, Vova phải mua chuộc tất cả mọi người.
Ở ví dụ thứ 3, quyết định tối ưu nhất là mua chuộc người thứ nhất, thứ ba, thứ năm, thứ 7 và thứ 9.
Hướng dẫn: Trong bài này, bạn được cho một đồ thị vô hướng với các đỉnh có trọng số. Và vấn đề là đi tính tổng các giá trị nhỏ nhất ở mỗi thành phần liên kết. Để làm được việc này, chúng ta chỉ việc sử dụng DFS và BFS vài lần.
Lời giải:

#include <bits/stdc++.h>
#define pb push_back
#define long long long
#define vl vector < long >
#define pll pair < long , long >
#define vll vector < pll >
#define x first
#define y second
#define ml map < long , long >
#define mll map < pll , long >
#define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
vl a[100005];
long mx,vv[100005],v[100005],ans;
void dfs(long node)
{
    long i;
    v[node]=1;
    mx=min(mx,vv[node]);
    for(i=0;i<a[node].size();++i)
    if(!v[a[node][i]])
    dfs(a[node][i]);
}
int main()
{
    io
    long n,m,x,y,i;
    cin>>n>>m;
    for(i=1;i<=n;++i)
    cin>>vv[i];
    for(i=0;i<m;++i)
    {
        cin>>x>>y;
        a[x].pb(y);
        a[y].pb(x);
    }
    for(i=1;i<=n;++i)
    if(!v[i])
    {
        mx=1e12;
        dfs(i);
        ans+=mx;
    }
    cout<<ans;
    return 0;
}