Advertisement
JouJoy

T

Dec 12th, 2021
865
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. #include <vector>
  2. #include<queue>
  3. #include<iostream>
  4. using namespace std;
  5. vector<int>v[100003];
  6. int ar[100004];
  7. bool visited[100004];
  8. long long int ans = 0;
  9. queue <int>q;
  10. int bfs(int src)
  11. {
  12.     q.push(src);
  13.     int minn = ar[src];
  14.     while (!q.empty())
  15.     {
  16.         int tmp = q.front();
  17.  
  18.         minn = min(minn, ar[tmp]);
  19.         int sz = v[tmp].size();
  20.         for (int i = 0; i <= sz - 1; i++)
  21.         {
  22.             int xxx = v[tmp][i];
  23.             if (visited[xxx] == false)
  24.             {
  25.                 visited[xxx] = true;
  26.                 q.push(xxx);
  27.             }
  28.         }
  29.         q.pop();
  30.     }
  31.     return minn;
  32. }
  33. int main()
  34. {
  35.     int x1, x2;
  36.     int n, m;
  37.     cin >> n >> m;
  38.     for (int i = 1; i <= n; i++)
  39.     {
  40.         cin >> ar[i];
  41.     }
  42.     for (int i = 1; i <= m; i++)
  43.     {
  44.         cin >> x1 >> x2;
  45.         v[x1].push_back(x2);
  46.         v[x2].push_back(x1);
  47.     }
  48.  
  49.     for (int i = 1; i <= n; i++)
  50.     {
  51.         if (visited[i] == false)
  52.         {
  53.             int xx = bfs(i);
  54.             ans = ans + xx;
  55.         }
  56.  
  57.     }
  58.     cout << ans << endl;
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement