fork(6) download
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long int ll;
  5. #define MOD 1000000007
  6. #define pb push_back
  7. #define pi pair<ll,ll>
  8. #define pii pair<ll,pair<ll,ll>>
  9. #define psi pair<string,ll>
  10. #define INF 10000000000000005
  11.  
  12. const ll MAX=1e5+1;
  13. pair <ll,pair<ll,ll> > e[MAX];
  14. ll a[MAX],size[MAX],m,n;
  15. set <pair<ll,ll> > s;
  16. set <pair<ll,ll> >::iterator it;
  17.  
  18. void initialize()
  19. {
  20. for(ll i=0;i<MAX;i++)
  21. {
  22. a[i]=i;
  23. size[i]=1;
  24. }
  25. }
  26.  
  27. ll root(ll i)
  28. {
  29. while(i!=a[i])
  30. {
  31. a[i]=a[a[i]];
  32. i=a[i];
  33. }
  34. return i;
  35. }
  36.  
  37. ll check()
  38. {
  39. ll i,tmp;
  40. tmp=root(1);
  41. for(i=1;i<=n;i++)
  42. {
  43. if(root(i)!=tmp)
  44. return 0;
  45. }
  46. return 1;
  47. }
  48.  
  49. void union1(ll x,ll y)
  50. {
  51. ll rx,ry;
  52. rx=root(x);
  53. ry=root(y);
  54. if(size[rx]>size[ry])
  55. {
  56. a[ry]=a[rx];
  57. size[rx]+=size[ry];
  58. }
  59. else
  60. {
  61. a[rx]=a[ry];
  62. size[ry]=size[rx];
  63. }
  64. }
  65.  
  66. ll kruskal(ll t)
  67. {
  68. ll i,x,y,c;
  69. for(i=0;i<m;i++)
  70. {
  71. x=e[i].second.first;
  72. y=e[i].second.second;
  73. c=e[i].first;
  74. if(root(x)!=root(y)&&c==t)
  75. {
  76. union1(x,y);
  77. s.insert(make_pair(min(x,y),max(x,y)));
  78. }
  79. }
  80. }
  81.  
  82. int main()
  83. {
  84. ios_base::sync_with_stdio(false);
  85. cin.tie(NULL);
  86. ll x,y,c,i,flag=0;
  87. cin>>n>>m;
  88. for(i=0;i<m;i++)
  89. {
  90. cin>>x>>y>>c;
  91. e[i]=make_pair(c,make_pair(x,y));
  92. }
  93. initialize();
  94. kruskal(3);
  95. kruskal(1);
  96. flag=check();
  97. if(flag==0)
  98. {
  99. cout<<"-1";
  100. }
  101. else
  102. {
  103. initialize();
  104. kruskal(3);
  105. kruskal(2);
  106. flag=check();
  107. if(flag==0)
  108. {
  109. cout<<"-1";
  110. }
  111. else
  112. {
  113. cout<<(m-s.size());
  114. }
  115. }
  116. return 0;
  117. }
  118.  
Success #stdin #stdout 0s 19968KB
stdin
Standard input is empty
stdout
Standard output is empty