Advertisement
fuadnafiz98

Untitled

Mar 2nd, 2021
590
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.94 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 100005;
  6.  
  7. vector<int> adj[maxn];
  8. bool visited[maxn];
  9. int c[maxn];
  10.  
  11. int bfs(int node) {
  12.     set<int> cost;
  13.     cost.insert(c[node]);
  14.     visited[node] = true;
  15.     queue<int> q;
  16.     q.push(node);
  17.     while(!q.empty()) {
  18.         int u = q.front();
  19.         q.pop();
  20.         for(int i = 0; i < (int)adj[u].size(); i++) {
  21.             if(!visited[adj[u][i]]) {
  22.                 q.push(adj[u][i]);
  23.                 visited[adj[u][i]] = true;
  24.                 cost.insert(c[adj[u][i]]);
  25.             }
  26.         }
  27.     }
  28.     set<int> :: iterator ret = cost.begin();
  29.     return *ret;
  30. }
  31.  
  32.  
  33. int main() {
  34.     int n, m;
  35.     cin >> n >> m;
  36.     for(int i = 0; i < n; i++) cin >> c[i];
  37.     for(int i = 0; i < m; i++) {
  38.         int u, v;
  39.         cin >> u >> v;
  40.         u--, v--;
  41.         adj[u].push_back(v);
  42.         adj[v].push_back(u);
  43.     }
  44.     long long ans = 0;
  45.     for(int i = 0; i < n; i++) {
  46.         if(!visited[i]) {
  47.             ans += (long long)bfs(i);
  48.             //cout << bfs(i) << endl;
  49.         }
  50.     }
  51.     cout << ans << '\n';
  52.     return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement