Advertisement
Guest User

Untitled

a guest
Jan 18th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define D 400007
  4.  
  5. using namespace std;
  6. typedef long long ll;
  7.  
  8. vector <ll> a[D], ta[D], ts;
  9. ll used[D], comp[D], ccount;
  10.  
  11. void topsort(ll v)
  12. {
  13. used[v] = true;
  14. for (ll to : a[v])
  15. if (!used[to])
  16. topsort(to);
  17. ts.push_back(v);
  18. }
  19. void dfs(ll v)
  20. {
  21. comp[v] = ccount;
  22. for (ll to : ta[v])
  23. if (!comp[to])
  24. dfs(to);
  25. }
  26.  
  27. void add(ll v1, ll v2)
  28. {
  29. a[v1].push_back(v2);
  30. ta[v2].push_back(v1);
  31. }
  32.  
  33. int main()
  34. {
  35. ios_base::sync_with_stdio(0);
  36. cin.tie(0); cout.tie(0);
  37. ll n, m, x1, x2;
  38. while (cin >> n >> m)
  39. {
  40. for (ll i = 0; i < D; i++)
  41. {
  42. a[i].clear();
  43. ta[i].clear();
  44. }
  45. ts.clear();
  46. memset(used, 0, sizeof(used));
  47. memset(comp, 0, sizeof(comp));
  48. ccount = 0;
  49.  
  50. for (ll i = 1; i <= m; i++)
  51. {
  52. cin >> x1 >> x2;
  53. if (x1 < 0 && x2 < 0)
  54. {
  55. x1 = -x1; x2 = -x2;
  56. add(x1, x2 + n);
  57. add(x2, x1 + n);
  58. }
  59. if (x1 > 0 && x2 > 0)
  60. {
  61. add(x1 + n, x2);
  62. add(x2 + n, x1);
  63. }
  64. if (x1 < 0 && x2 > 0)
  65. {
  66. x1 = -x1;
  67. add(x1, x2);
  68. add(x2 + n, x1 + n);
  69. }
  70. if (x1 > 0 && x2 < 0)
  71. {
  72. x2 = -x2;
  73. add(x1 + n, x2 + n);
  74. add(x2, x1);
  75. }
  76. }
  77. topsort(1);
  78. if (used[1 + n])
  79. {
  80. cout << "no" << endl, 0;
  81. continue;
  82. }
  83.  
  84. for (ll i = 2; i <= n * 2; i++)
  85. if (!used[i])
  86. topsort(i);
  87. reverse(ts.begin(), ts.end());
  88.  
  89. for (ll v : ts)
  90. if (!comp[v])
  91. {
  92. ccount++;
  93. dfs(v);
  94. }
  95. for (ll i = 1; i <= n; i++)
  96. if (comp[i] == comp[i + n])
  97. {
  98. cout << "no" << endl, 0;
  99. continue;
  100. }
  101.  
  102. cout << "yes" << endl;
  103. }
  104. return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement