fork(6) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <memory.h>
  4.  
  5. using namespace std;
  6.  
  7. const int MAX_N = (int) 1e5;
  8.  
  9. vector<int> g[MAX_N];
  10. int a[MAX_N];
  11. bool inA[MAX_N];
  12.  
  13. vector<int> ts;
  14. bool used[MAX_N];
  15.  
  16. void dfs1(int v) {
  17.     if (used[v]) {
  18.         return;
  19.     }
  20.     used[v] = true;
  21.     for (int i = 0; i < g[v].size(); i++) {
  22.         dfs1(g[v][i]);
  23.     }
  24.     ts.push_back(v);
  25. }
  26.  
  27. int r[MAX_N];
  28. void dfs2(int v, int x) {
  29.     if (r[v] != -1) {
  30.         return;
  31.     }
  32.     r[v] = x;
  33.     for (int i = 0; i < g[v].size(); i++) {
  34.         dfs2(g[v][i], x);
  35.     }
  36. }
  37.  
  38. int main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(0);
  41.     int n, m;
  42.     cin >> n >> m;
  43.     for (int i = 0; i < m; i++) {
  44.         int x, y;
  45.         cin >> x >> y;
  46.         --x;
  47.         --y;
  48.         g[x].push_back(y);
  49.     }
  50.  
  51.     for (int i = 0; i < n; i++) {
  52.         cin >> a[i];
  53.         --a[i];
  54.         inA[a[i]] = true;
  55.     }
  56.  
  57.     for (int i = 0; i < n; i++) {
  58.         if (!used[i]) {
  59.             dfs1(i);
  60.         }
  61.     }
  62.  
  63.     memset(r, -1, sizeof(r));
  64.     vector<int> ans;
  65.     for (int i = 0; i < n; i++) {
  66.         if (inA[ts[i]]) {
  67.             dfs2(ts[i], ts[i]);
  68.             ans.push_back(ts[i]);
  69.         }
  70.     }
  71.  
  72.     for (int i = 0; i < n; i++) {
  73.         if (r[i] != a[i]) {
  74.             cout << -1;
  75.             return 0;
  76.         }
  77.     }
  78.  
  79.  
  80.     cout << ans.size() << "\n";
  81.     for (int i = 0; i < ans.size(); i++) {
  82.         cout << ans[i] + 1 << "\n";
  83.     }
  84.  
  85.  
  86.     return 0;
  87. }
Runtime error #stdin #stdout 0s 5604KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Nwydx2
language:
C++ (gcc 8.3)
created:
8 years 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!