SHARE
TWEET

Untitled

a guest Oct 21st, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n,mn,ind;
  6. vector<int> p;
  7. vector<vector<int>> g;
  8. vector<bool> used;
  9. vector<pair<int,int>> ans;
  10. vector<int> comp;
  11.  
  12. void dfs (int v) {
  13.     if(p[v]<=mn || mn==-1){
  14.         mn=p[v];
  15.         ind=v;
  16.     }
  17.     used[v] = true;
  18.     comp.push_back (v);
  19.     for (size_t i=0; i<g[v].size(); ++i) {
  20.         int to = g[v][i];
  21.         if (! used[to])
  22.             dfs (to);
  23.     }
  24. }
  25.  
  26. void find_comps() {
  27.     for (int i=0; i<n; ++i)
  28.         used[i] = false;
  29.     for (int i=0; i<n; ++i)
  30.         if (! used[i]) {
  31.             mn=-1;
  32.             comp.clear();
  33.             dfs (i);
  34.             //cout << "Component:";
  35.             //for (size_t j=0; j<comp.size(); ++j)
  36.             //  cout << ' ' << comp[j];
  37.             //cout << endl;
  38.             ans.push_back({mn,ind});
  39.         }
  40. }
  41.  
  42. main(){
  43.     int m;
  44.     cin>>n>>m;
  45.     p.resize(n,0);
  46.     g.resize(n);
  47.     used.resize(n);
  48.     for(int i=0;i<n;i++)
  49.         cin>>p[i];
  50.     for(int i=0;i<m;i++){
  51.         int v,u;
  52.         cin>>v>>u;v--;u--;
  53.         g[v].push_back(u);
  54.         g[u].push_back(v);
  55.     }
  56.     find_comps();
  57.     sort(ans.begin(),ans.end());
  58.     cout<<ans.size()-1<<'\n';
  59.     for(int i=1;i<ans.size();i++){
  60.         cout<<ans[0].second+1<<' '<<ans[i].second+1<<'\n';
  61.     }
  62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top