Untitled

 avatar
unknown
c_cpp
2 years ago
2.1 kB
9
Indexable
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
using namespace std ;
const int maxn = 1e6+7;
int par[maxn] , sz[maxn] , p[maxn];
bool mark[maxn] , mark2[maxn];
vector<int> v[maxn] , vec[maxn];

void dbg(){
     cerr << endl;
}
template<typename H, typename... T> void dbg(H h, T... t){
     cerr << h << ", ";
     dbg(t...);
}
#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)

int get(int nw){
    return (nw == par[nw] ? nw : par[nw] = get(par[nw]));
}
bool merge(int u , int v){
    u = get(u);
    v = get(v);
    if(u == v) return false;
    if(sz[u] > sz[v]) swap(u , v);
    sz[v] += sz[u];
    par[u] = v;
    return true;
}
int main(){
    ios;
    int n , m;
    cin >> n >> m;
    for(int i = 0 ; i < n ; i++) sz[i] = 1 , par[i] = i;
    for(int i = 0 ; i < n; i++){
        cin >> p[i];
    }
    for(int i = 0 ; i < m ; i++){
        int u ,v;
        cin >> u >> v;
        --u;--v;
        merge(u , v);
    }
    for(int i = 0 ; i < n ; i++){
        v[get(i)].push_back(i); // saving the indexes
        vec[get(i)].push_back(p[i]); //saving the values
    }
   //  er(v[get(3)].size());
    
    for(int i = 0 ; i < n ; i++){
        if(!mark[get(i)]){
            mark[get(i)] = true;
            sort(v[get(i)].begin() , v[get(i)].end());
            sort(vec[get(i)].begin() , vec[get(i)].end());
            reverse(vec[get(i)].begin() , vec[get(i)].end());
        }
    }
    /*
      for(int i = 0 ; i < n; i++){
        for(int j = 0 ; j < v[get(i)].size() ; j++) cout << v[get(i)][j] << ' ';
    }
    */
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < v[get(i)].size() ; j++){
            if(v[get(i)][j] == i && !mark2[v[get(i)][j]]){ 
                mark2[v[get(i)][j]] = true;
                cout << vec[get(i)][j] << ' ';
                //d[get(i)].pop_front();
                //d[get(i)].pop_front();
                break;
            }
        }
    }
    return 0;
}
Editor is loading...