fork download
  1. #include <map>
  2. #include <set>
  3. #include <cmath>
  4. #include <ctime>
  5. #include <deque>
  6. #include <queue>
  7. #include <stack>
  8. #include <bitset>
  9. #include <cctype>
  10. #include <cstdio>
  11. #include <vector>
  12. #include <cassert>
  13. #include <complex>
  14. #include <cstdlib>
  15. #include <cstring>
  16. #include <fstream>
  17. #include <iomanip>
  18. #include <sstream>
  19. #include <iostream>
  20. #include <algorithm>
  21.  
  22. using namespace std;
  23.  
  24. #define mp make_pair
  25. #define pb push_back
  26. #define ll long long
  27. #define fi first
  28. #define se second
  29.  
  30. #define all(a) a.begin(),a.end()
  31. #define fill(a,v) memset(a,v,sizeof(a))
  32.  
  33. #define bitcount __buitin_popcount
  34. #define gcd __gcd
  35.  
  36.  
  37. typedef vector<int> vi;
  38. typedef pair<int,int> pii;
  39. typedef vector<vi > vvi;
  40.  
  41. map<pii,pii> dad;
  42. map<pii,ll> rnk;
  43. void UNION(pii x,pii y)
  44. {
  45. if(rnk[x] > rnk[y])
  46. dad[y] = x;
  47. else
  48. {
  49. dad[x] = y;
  50. if(rnk[y] == rnk[x])
  51. rnk[x]++;
  52. }
  53. }
  54. pii FIND(pii x)
  55. {
  56. if(dad[x] != x)
  57. {
  58. dad[x] = FIND(dad[x]);
  59. }
  60. else return x;
  61. }
  62. int main()
  63. {
  64.  
  65.  
  66. ll n;
  67. while(cin >> n)
  68. {
  69. if(n == -1) return 0;
  70.  
  71. int m;cin >> m;
  72. pii query[m];
  73. string parity[m];
  74.  
  75. for(int i = 0 ; i < m ; ++i)
  76. {
  77. cin >> query[i].fi >> query[i].se;
  78. cin >> parity[i];
  79. }
  80.  
  81. int cnt = 0;
  82. for(int i = 0 ; i < m ; ++i)
  83. {
  84. int x = query[i].fi,y = query[i].se;
  85. pii s= mp(x-1,0),s1 = mp(x-1,1),d = mp(y,0),d1 = mp(y,1);
  86. dad[s] = s;
  87. rnk[s] = 0;
  88. dad[s1] = s1;
  89. rnk[s1] = 0;
  90. dad[d] = d;rnk[d] = 0;
  91. dad[d1] = d1;rnk[d1] = 0;
  92. }
  93. for(int i = 0 ; i < m ; ++i)
  94. {
  95. int x = query[i].fi,y = query[i].se;
  96. pii s= mp(x-1,0),s1 = mp(x-1,1),d = mp(y,0),d1 = mp(y,1);
  97.  
  98. if(parity[i] == "even")
  99. {
  100. UNION(FIND(s),FIND(d));
  101. UNION(FIND(s1),FIND(d1));
  102. }
  103. else
  104. {
  105. UNION(FIND(s1),FIND(d));
  106. UNION(FIND(s),FIND(d1));
  107. }
  108.  
  109. if(FIND(s) == FIND(s1)) goto p;
  110. else if(FIND(d) == FIND(d1) ) goto p;
  111. cnt++;
  112. }
  113.  
  114. p: cout << cnt << endl;
  115. }
  116.  
  117. return 0;
  118. }
  119.  
Success #stdin #stdout 0s 3304KB
stdin
Standard input is empty
stdout
Standard output is empty