HackerEarth 3 types problem solution

In this HackerEarth 3 types problem solution Let’s consider some weird country with N cities and M bidirectional roads of 3 types. It’s weird because of some unusual rules about using these roads: men can use roads of types 1 and 3 only and women can use roads of types 2 and 3 only. Please answer the following very interesting question: what is a maximum number of roads it’s possible to destroy that the country will be still connected for both men and women? A connected country is a country where it’s possible to travel from any city to any other using existing roads.

HackerEarth 3 types of problem solution.

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a,b,c,ans;
int w[1<<20];
int get(int x)
{
  if (w[x]==x)
    return x;
  return w[x]=get(w[x]);
}
void merge(int a,int b)
{
  w[a]=b;
}
int W[1<<20][3];
int get1(int x,int y)
{
  if (W[x][y]==x)
    return x;
  return get1(W[x][y],y);
}
void merge1(int a,int b,int c)
{
  W[a][c]=b;
}
int main(){
ios_base::sync_with_stdio(0);
//cin.tie(0);
cin>>n>>m;
for (int i=1;i<=n;i++)
  w[i]=W[i][1]=W[i][2]=i;
  
for (int i=1;i<=m;i++)
{
  cin>>a>>b>>c;
  
  for (int j=1;j<=2;j++)
    if (c&j)
    {
      int ta,tb;
      ta=get1(a,j);
      tb=get1(b,j);
      if (ta==tb)
        continue;
      merge1(ta,tb,j);
    }
    
  if (c!=3)
    continue;
  a=get(a);
  b=get(b);
  if (a==b)
    continue;
  merge(a,b);
  ++ans;
}
ans=(n-1-ans)*2+ans;
int cnt=0;
for (int i=1;i<=n;i++)
  for (int j=1;j<=2;j++)
    if (W[i][j]==i)
      ++cnt;
      
if (cnt>2)
{
  cout<<-1<<endl;
  return 0;
}
cout<<m-ans<<endl;
return 0;}

coding problems solutions