Guest User

Untitled

a guest
Nov 23rd, 2017
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <queue>
  5. #include <set>
  6. #include <algorithm>
  7. using namespace std;
  8. vector<vector<int>> rd;
  9. vector<bool> u;
  10. vector<vector<int>> g(10000000);
  11. void dfs(int v)
  12. {
  13. if(u[v])
  14. {
  15. return;;
  16. }
  17. u[v] = true;
  18. rd.back().push_back(v);
  19. for(auto i : g[v])
  20. {
  21. dfs(i);
  22. }
  23. }
  24.  
  25. int main()
  26. {
  27. int n, m;
  28. cin >> n >> m;
  29. g.resize(n + 1);
  30. vector<int> d(n + 1);
  31. set<int> all;
  32. u.resize(n + 1);
  33. for(int i = 1; i <= n; ++i)
  34. {
  35. all.insert(i);
  36. cin >> d[i];
  37. }
  38. for(int i = 0; i < m; ++i)
  39. {
  40. int a, b;
  41. cin >> a >> b;
  42. g[a].push_back(b);
  43. g[b].push_back(a);
  44. all.erase(a);
  45. all.erase(b);
  46. }
  47. for(auto i : all)
  48. {
  49. g[i].push_back(i);
  50. }
  51. long long ans = 0;
  52. for(int i = 1; i <= n; ++i)
  53. {
  54. if(!u[i])
  55. {
  56. rd.push_back({});
  57. dfs(i);
  58. int mn = 1000 * 1000 * 1000 + 228;
  59. for(auto j : rd.back())
  60. {
  61. mn = min(d[j], mn);
  62. }
  63. ans += mn;
  64. }
  65. }
  66. cout << ans;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment