fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define bigInt __int128
  5. #define PI 3.14159265
  6. #define allr(v) v.rbegin(), v.rend()
  7. #define all(v) v.begin(), v.end()
  8. #define Sabry                         \
  9.      std::ios::sync_with_stdio(false), ios_base::sync_with_stdio(false); \
  10.     cin.tie(NULL), cout.tie(NULL);
  11. // int dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};
  12. int dx1[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy1[] = {-1, 0, 1, -1, 1, -1, 0, 1};
  13. const int MOD = 1e9 + 7;
  14. const int MAX = 2e5 + 5;
  15. const int INF = 1e18;
  16. const long double EPS = 1e-7; 
  17.  
  18.  
  19. ///
  20. #ifndef ONLINE_JUDGE
  21. auto f1 = freopen(R"(input.txt)", "r", stdin);
  22. auto f2 = freopen(R"(output.txt)", "w", stdout);
  23. #endif
  24. ///
  25.  
  26. ///////////////
  27. int modpow(int b , int p , int mod = MOD){
  28.     if (!p) return 1;
  29.     int z = modpow(b , p>>1 , mod);
  30.     z = ((z*z)%mod * (p&1 ? b : 1))%mod; 
  31.     return z;
  32. }
  33.  
  34. int inv(int a) {
  35.   return a <= 1 ? a : MOD - (int)(MOD/a) * inv(MOD % a) % MOD;
  36. }
  37.  
  38. ///////////////
  39. void preCompute() {
  40.  
  41. }
  42.  
  43. vector<int> adj[MAX], child[MAX];
  44. int submin[MAX], a[MAX];
  45. vector<int> ord;
  46.  
  47. void dfs1(int u, int p) {
  48.     submin[u] = u;
  49.     for (int v : adj[u]) {
  50.         if (v == p) continue;
  51.         child[u].push_back(v);
  52.         dfs1(v, u);
  53.         submin[u] = min(submin[u], submin[v]);
  54.     }
  55. }
  56.  
  57.  
  58.  
  59. // void dfs2(int u, int p) {
  60. //     a[u] = val++;
  61. //     for(auto v : adj[u])
  62. //         if(v != p)
  63. //             dfs2(v, u);
  64.  
  65. // }
  66.  
  67. void sol() {
  68.     int n, x; cin >> n >> x;
  69.     for(int i=0;i<n-1;i++){
  70.         int u, v; cin >> u >> v;
  71.         adj[u].push_back(v);
  72.         adj[v].push_back(u);
  73.     }
  74.  
  75.     dfs1(x, -1);
  76.     // dfs2(x, -1);
  77.  
  78.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  79.  
  80.     pq.push({submin[x], x});
  81.  
  82.     while(!pq.empty()) {
  83.         auto [val, u] = pq.top(); pq.pop();
  84.         ord.push_back(u);
  85.         for(auto v : child[u]){
  86.             pq.push({submin[v], v});
  87.         }
  88.     }
  89.  
  90.     for(int i=0;i<n;i++){
  91.         a[ord[i]] = i+1;
  92.     }
  93.  
  94.     for(int i=1;i<=n;i++){
  95.         cout << a[i] << " ";
  96.     }
  97. }
  98.  
  99.  
  100.  
  101. signed main()
  102. {
  103.     Sabry;
  104.     preCompute();
  105.     int t = 1;
  106.     // cin >> t;
  107.     // int cnt = 1;	
  108.     while (t--)
  109.     {
  110.         // cout << "Case " << cnt << ": ";
  111.         sol();
  112.         // cnt++;
  113.     }
  114.     return 0;
  115. }
Success #stdin #stdout 0.01s 15820KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R76Tii
language:
C++ (gcc 8.3)
created:
19 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!