Advertisement
Guest User

Untitled

a guest
Mar 29th, 2020
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.29 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define NM 1005
  4. int n, t[NM], nr[NM], rez;
  5. int cc[NM], nod_cur, ff[NM];
  6. set<int> s;
  7. vector<int> v[NM];
  8. bitset<NM> viz;
  9. void dfs1(int nod)
  10. {
  11. viz[nod] = 1;
  12. cc[nod] = nod_cur;
  13. ff[nod_cur]++;
  14. for(auto it:v[nod])
  15. if(!viz[it])
  16. dfs1(it);
  17. }
  18. void dfs(int nod)
  19. {
  20. viz[nod] = 1;
  21. for(auto it:v[nod])
  22. if(!viz[it])
  23. {
  24. dfs(it);
  25. nr[nod]+=nr[it];
  26. }
  27. nr[nod]++;
  28. s.insert(ff[cc[nod]] - nr[nod]);
  29. }
  30. int main()
  31. {
  32. cin >> n;
  33. for(int i=1; i<=n; i++)
  34. {
  35. cin >> t[i];
  36. if(t[i])
  37. {
  38. v[i].push_back(t[i]);
  39. v[t[i]].push_back(i);
  40. }
  41. }
  42. for(int i=1; i<=n; i++)
  43. if(!viz[i])
  44. {
  45. nod_cur = i;
  46. cc[i] = i;
  47. dfs1(i);
  48. }
  49. for(int i=1; i<=n; i++)
  50. viz[i] = 0;
  51. for(int i=1; i<=n; i++)
  52. if(t[i] == 0)
  53. {
  54. s.clear();
  55. dfs(i);
  56. for(int j=0; j<=n; j++)
  57. if(s.find(j) == s.end())
  58. {
  59. rez^=j;
  60. break;
  61. }
  62. }
  63. if(rez!=0)
  64. cout << "YES";
  65. else cout << "NO";
  66. return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement