fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main() {
  6.     // Fast I/O
  7.     ios_base::sync_with_stdio(false);
  8.     cin.tie(NULL);
  9.  
  10.     int T;
  11.     cin >> T;
  12.     while(T--) {
  13.         int n;
  14.         cin >> n;
  15.  
  16.         // 1-based indexing: sizes are n + 1
  17.         vector<int> a(n + 1);
  18.         vector<ll> cost(n + 1);
  19.         vector<int> in(n + 1, 0);
  20.  
  21.         // Read 'a' array (1-based)
  22.         for(int i = 1; i <= n; i++) {
  23.             cin >> a[i];
  24.             in[a[i]]++;
  25.         }
  26.  
  27.         // Read 'cost' array (1-based)
  28.         for(int i = 1; i <= n; i++) {
  29.             cin >> cost[i];
  30.         }
  31.  
  32.         queue<int> q;
  33.         vector<int> ans;
  34.  
  35.         // FIXED: Initialize the queue with nodes having in-degree 0
  36.         for(int i = 1; i <= n; i++) {
  37.             if(in[i] == 0) {
  38.                 q.push(i);
  39.             }
  40.         }
  41.  
  42.         // Kahn's Algorithm / Topological Sort
  43.         while(!q.empty()){
  44.             int u = q.front();
  45.             q.pop();
  46.             ans.push_back(u);
  47.  
  48.             int v = a[u];
  49.             in[v]--;
  50.             if(in[v] == 0) {
  51.                 q.push(v);
  52.             }
  53.         }
  54.  
  55.         // FIXED: Size needs to be n + 1 to support 1-based indexing
  56.         vector<int> vis(n + 1, 0);
  57.  
  58.         for(int i = 1; i <= n; i++){
  59.             if(in[i] == 0 || vis[i]) continue;
  60.  
  61.             vector<int> cycle;
  62.             int cur = i;
  63.  
  64.             while(!vis[cur]){
  65.                 vis[cur] = 1;
  66.                 cycle.push_back(cur);
  67.                 cur = a[cur];
  68.             }
  69.  
  70.             int pos = 0;
  71.             for(int j = 1; j < cycle.size(); j++){
  72.                 if(cost[cycle[j]] < cost[cycle[pos]]) {
  73.                     pos = j;
  74.                 }
  75.             }
  76.  
  77.             // Push cycle elements so the minimum cost node is placed last
  78.             for(int j = pos + 1; j < cycle.size(); j++){
  79.                 ans.push_back(cycle[j]);
  80.             }
  81.  
  82.             for(int j = 0; j <= pos; j++){
  83.                 ans.push_back(cycle[j]);
  84.             }
  85.         }
  86.  
  87.         for (int x : ans) {
  88.             cout << x << " ";
  89.         }
  90.         // FIXED: Print a newline after each test case
  91.         cout << "\n";
  92.     }
  93.     return 0;
  94. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
8
3
2 3 2
6 6 1
8
2 1 4 3 6 5 8 7
1 2 1 2 2 1 2 1
5
2 1 1 1 1
9 8 1 1 1
2
2 1
1000000000 999999999
7
2 3 2 6 4 4 3
1 2 3 4 5 6 7
5
3 4 4 1 3
3 4 5 6 7
3
2 1 1
1 2 2
4
2 1 4 1
1 1 1 1
stdout
copy 
1 2 3 
2 1 4 3 5 6 7 8 
3 4 5 1 2 
1 2 
1 5 7 3 2 6 4 
2 5 3 4 1 
3 2 1 
3 4 2 1
https://ideone.com/9BBO1H
language:
C++ (gcc 8.3)
created:
4 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!