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 problem solution


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