Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n,mn,ind;
- vector<int> p;
- vector<vector<int>> g;
- vector<bool> used;
- vector<pair<int,int>> ans;
- vector<int> comp;
- void dfs (int v) {
- if(p[v]<=mn || mn==-1){
- mn=p[v];
- ind=v;
- }
- used[v] = true;
- comp.push_back (v);
- for (size_t i=0; i<g[v].size(); ++i) {
- int to = g[v][i];
- if (! used[to])
- dfs (to);
- }
- }
- void find_comps() {
- for (int i=0; i<n; ++i)
- used[i] = false;
- for (int i=0; i<n; ++i)
- if (! used[i]) {
- mn=-1;
- comp.clear();
- dfs (i);
- //cout << "Component:";
- //for (size_t j=0; j<comp.size(); ++j)
- // cout << ' ' << comp[j];
- //cout << endl;
- ans.push_back({mn,ind});
- }
- }
- main(){
- int m;
- cin>>n>>m;
- p.resize(n,0);
- g.resize(n);
- used.resize(n);
- for(int i=0;i<n;i++)
- cin>>p[i];
- for(int i=0;i<m;i++){
- int v,u;
- cin>>v>>u;v--;u--;
- g[v].push_back(u);
- g[u].push_back(v);
- }
- find_comps();
- sort(ans.begin(),ans.end());
- cout<<ans.size()-1<<'\n';
- for(int i=1;i<ans.size();i++){
- cout<<ans[0].second+1<<' '<<ans[i].second+1<<'\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement