fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int T;
  9.     cin >> T;
  10.  
  11.     while (T--) {
  12.  
  13.         int n;
  14.         cin >> n;
  15.  
  16.         vector<int> a(n + 1);
  17.         vector<long long> cost(n + 1);
  18.         vector<int> indeg(n + 1, 0);
  19.  
  20.         // Read graph
  21.         for (int i = 1; i <= n; i++) {
  22.             cin >> a[i];
  23.             indeg[a[i]]++;
  24.         }
  25.  
  26.         // Read costs
  27.         for (int i = 1; i <= n; i++)
  28.             cin >> cost[i];
  29.  
  30.         queue<int> q;
  31.         vector<int> ans;
  32.  
  33.         // Put all indegree-0 nodes into queue
  34.         for (int i = 1; i <= n; i++) {
  35.             if (indeg[i] == 0)
  36.                 q.push(i);
  37.         }
  38.  
  39.         // Kahn's Algorithm
  40.         while (!q.empty()) {
  41.  
  42.             int u = q.front();
  43.             q.pop();
  44.  
  45.             ans.push_back(u);
  46.  
  47.             int v = a[u];
  48.  
  49.             indeg[v]--;
  50.  
  51.             if (indeg[v] == 0)
  52.                 q.push(v);
  53.         }
  54.  
  55.         // Visit remaining cycles
  56.         vector<int> vis(n + 1, 0);
  57.  
  58.         for (int i = 1; i <= n; i++) {
  59.  
  60.             // Already removed or already processed
  61.             if (indeg[i] == 0 || vis[i])
  62.                 continue;
  63.  
  64.             vector<int> cycle;
  65.  
  66.             int cur = i;
  67.  
  68.             // Walk around the cycle
  69.             while (!vis[cur]) {
  70.                 vis[cur] = 1;
  71.                 cycle.push_back(cur);
  72.                 cur = a[cur];
  73.             }
  74.  
  75.             // Find minimum-cost node
  76.             int pos = 0;
  77.  
  78.             for (int j = 1; j < cycle.size(); j++) {
  79.                 if (cost[cycle[j]] < cost[cycle[pos]])
  80.                     pos = j;
  81.             }
  82.  
  83.             // Print after minimum-cost node
  84.             for (int j = pos + 1; j < cycle.size(); j++)
  85.                 ans.push_back(cycle[j]);
  86.  
  87.             for (int j = 0; j <= pos; j++)
  88.                 ans.push_back(cycle[j]);
  89.         }
  90.  
  91.         for (int x : ans)
  92.             cout << x << " ";
  93.  
  94.         cout << "\n";
  95.     }
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 0s 5320KB
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/wWaCYX
language:
C++ (gcc 8.3)
created:
4 hours 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!