fork(9) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ErzVJl
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!