Submission #3459908

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int N,M,x,y,cv = 0,ce = 0,visited[100010] = {0};
ll C[100010],mi = 1e18,sum = 0;
vector<vector<int>> v(100010);

void dfs(int n){
	visited[n] = 1;
	cv++;
	sum += C[n];
	mi = min(mi,C[n]);
	for(int i=0;i<v[n].size();i++){
		int s = v[n][i];
		ce++;
		if(visited[s]==0){
			dfs(s);
		}
	}
}

int main(){
	cin >> N >> M;
	for(int i=1;i<=N;i++){
		cin >> C[i];
	}
	for(int i=0;i<M;i++){
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	ll ans = 0;
	for(int i=1;i<=N;i++){
		if(visited[i]==0){
			sum = 0; mi = 1e18; cv = 0; ce = 0;
			dfs(i);
			ce /= 2;
			if(cv-1==ce) ans += sum-mi;
			else ans += sum;
		}
	}
	cout << ans << endl;
}

Submission Info

Judge Result