Untitled
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...