Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- const int maxn = 100005;
- vector<int> adj[maxn];
- bool visited[maxn];
- int c[maxn];
- int bfs(int node) {
- set<int> cost;
- cost.insert(c[node]);
- visited[node] = true;
- queue<int> q;
- q.push(node);
- while(!q.empty()) {
- int u = q.front();
- q.pop();
- for(int i = 0; i < (int)adj[u].size(); i++) {
- if(!visited[adj[u][i]]) {
- q.push(adj[u][i]);
- visited[adj[u][i]] = true;
- cost.insert(c[adj[u][i]]);
- }
- }
- }
- set<int> :: iterator ret = cost.begin();
- return *ret;
- }
- int main() {
- int n, m;
- cin >> n >> m;
- for(int i = 0; i < n; i++) cin >> c[i];
- for(int i = 0; i < m; i++) {
- int u, v;
- cin >> u >> v;
- u--, v--;
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- long long ans = 0;
- for(int i = 0; i < n; i++) {
- if(!visited[i]) {
- ans += (long long)bfs(i);
- //cout << bfs(i) << endl;
- }
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement