Advertisement
Korotkodul

Graph

Aug 9th, 2022 (edited)
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. #define vec vector
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v){
  17.     for (auto x: v) cout<<x<<' ';
  18.     cout<<"\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v){
  22.     for (auto x: v) cout<<x<<' ';
  23.     cout<<"\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v){
  28.     for (auto x: v) cv(x);
  29.     cout<<"\n";
  30. }
  31.  
  32. void cvb(vector <bool> v){
  33.     for (bool x: v) cout<<x<<' ';
  34.     cout<<"\n";
  35. }
  36.  
  37. void cvs(vector <string>  v){
  38.     for (auto a: v){
  39.         cout<<a<<"\n";
  40.     }
  41. }
  42.  
  43. void cvp(vector <pii> a){
  44.     for (auto p: a){
  45.         cout<<p.first<<' '<<p.second<<"\n";
  46.     }
  47.     cout<<"\n";
  48. }
  49.  
  50. vector <vector <int> > G;
  51. vector <bool> wch;//watch
  52.  
  53. /*
  54. решение : dfs-м для каждой вершины посчитать, сколько ее потомков явлюятся под подозрением.
  55. ответ = первая вершина снизу, среди потомков к-рой содержатся ВСЕ за к-рыми надо следить.
  56. Это мы понимаем на стадии clr[v] = 2
  57. */
  58.  
  59. bool sh = 0;
  60.  
  61.  
  62. #include <sstream>
  63. int main()
  64. {
  65.     ios::sync_with_stdio(0);
  66.     cin.tie(0);
  67.     cout.tie(0);
  68.     string s;
  69.     getline(cin, s);
  70.     int n = stoi(s);
  71.      G.assign(n, vector <int> (0)); wch.assign(n,0);
  72.     string bd="";
  73.     //getline(cin, "\n")
  74.     getline(cin, bd);
  75.  
  76.     int id=0;
  77.     while (id < bd.size()){
  78.         string nmb="";
  79.         while (id < bd.size() && bd[id] != ' '){
  80.             nmb += bd[id];
  81.             id++;
  82.         }
  83.         int d = stoi(nmb);
  84.         wch[d-1]=1;
  85.         id++;
  86.     }
  87.  
  88.     /*string s="";
  89.     while (s !=  "\n"){
  90.         cin>>s;
  91.         bd += s + ' ';
  92.     }*/
  93.  
  94.  
  95.  
  96.  
  97.     for (int  i = 1; i < n; ++i){
  98.         int to; cin>>to; to--; G[to].push_back(i);
  99.     }
  100.  
  101.     if (sh){
  102.         cout<<"G\n";
  103.         //cvv(G);
  104.         cout<<"wch\n";
  105.         for (bool i: wch) cout<<i<<' '; cout<<"\n";
  106.         cout<<"n bd = "<<n<<'\n'<<bd<<"\n";
  107.     }
  108.  
  109. }
  110. /*
  111.  
  112. 8
  113. 3 6 1
  114. 1 1 2 4 5 1 1
  115.  
  116. 8
  117. 3 6
  118. 1 1 2 4 5 1 1
  119. */
  120.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement