Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <queue>
- #include <set>
- #include <algorithm>
- using namespace std;
- vector<vector<int>> rd;
- vector<bool> u;
- vector<vector<int>> g(10000000);
- void dfs(int v)
- {
- if(u[v])
- {
- return;;
- }
- u[v] = true;
- rd.back().push_back(v);
- for(auto i : g[v])
- {
- dfs(i);
- }
- }
- int main()
- {
- int n, m;
- cin >> n >> m;
- g.resize(n + 1);
- vector<int> d(n + 1);
- set<int> all;
- u.resize(n + 1);
- for(int i = 1; i <= n; ++i)
- {
- all.insert(i);
- cin >> d[i];
- }
- for(int i = 0; i < m; ++i)
- {
- int a, b;
- cin >> a >> b;
- g[a].push_back(b);
- g[b].push_back(a);
- all.erase(a);
- all.erase(b);
- }
- for(auto i : all)
- {
- g[i].push_back(i);
- }
- long long ans = 0;
- for(int i = 1; i <= n; ++i)
- {
- if(!u[i])
- {
- rd.push_back({});
- dfs(i);
- int mn = 1000 * 1000 * 1000 + 228;
- for(auto j : rd.back())
- {
- mn = min(d[j], mn);
- }
- ans += mn;
- }
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment