Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include<queue>
- #include<iostream>
- using namespace std;
- vector<int>v[100003];
- int ar[100004];
- bool visited[100004];
- long long int ans = 0;
- queue <int>q;
- int bfs(int src)
- {
- q.push(src);
- int minn = ar[src];
- while (!q.empty())
- {
- int tmp = q.front();
- minn = min(minn, ar[tmp]);
- int sz = v[tmp].size();
- for (int i = 0; i <= sz - 1; i++)
- {
- int xxx = v[tmp][i];
- if (visited[xxx] == false)
- {
- visited[xxx] = true;
- q.push(xxx);
- }
- }
- q.pop();
- }
- return minn;
- }
- int main()
- {
- int x1, x2;
- int n, m;
- cin >> n >> m;
- for (int i = 1; i <= n; i++)
- {
- cin >> ar[i];
- }
- for (int i = 1; i <= m; i++)
- {
- cin >> x1 >> x2;
- v[x1].push_back(x2);
- v[x2].push_back(x1);
- }
- for (int i = 1; i <= n; i++)
- {
- if (visited[i] == false)
- {
- int xx = bfs(i);
- ans = ans + xx;
- }
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement