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;}

## 0 Comments