# HackerEarth Feasible relations problem solution

In this HackerEarth Feasible relations problem solution As a programmer, you sometimes have to deal with some math and this is the time to do it. You are given a list of binary relations, equalities and inequalities, like a = b, a != d, b = c etc. Your task is to output YES if you can assign integers to input variables in such a way, that you can satisfy all equalities and inequalities. Otherwise you should output NO.

## HackerEarth Feasible relations problem solution.

`#include <iostream>#include <cstdio>#include <string>#include <sstream> #include <vector>#include <set>#include <map>#include <queue>#include <stack>#include <cmath>#include <algorithm>#include <cstring>#include <ctime>#include <cassert>using namespace std;#define pb push_back#define mp make_pair#define pii pair<int,int>#define vi vector<int>#define SZ(x) ((int)(x.size()))#define fi first#define se second#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))#define IN(x,y) ((y).find((x))!=(y).end())#define ALL(t) t.begin(),t.end()#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)#define REMAX(a,b) (a)=max((a),(b));#define REMIN(a,b) (a)=min((a),(b));#define DBG cerr << "debug here" << endl;#define DBGV(vari) cerr << #vari<< " = "<< (vari) <<endl;typedef long long ll;const int MAXN = 1000000;vi g[MAXN];int cc[MAXN];bool visited[MAXN];void dfs(int v, int id){    visited[v] = 1;    cc[v] = id;    FOR(i, g[v].size())    {        int u = g[v][i];        if(!visited[u]) dfs(u, id);    }}int main()    {    ios_base::sync_with_stdio(0);    int t;    cin >> t;    while(t--)    {        int n, m;        cin >> n >> m;        FOR(i, n) g[i].clear();        FOR(i, n) visited[i] = 0;        vector<pii> bad_edges;        FOR(i, m)        {            int v, u;            string relation;            cin >> v >> relation >> u;            --v; --u;            if(relation == "=")            {                g[v].pb(u);                g[u].pb(v);            }            else            {                bad_edges.pb(mp(v, u));            }        }        FOR(i, n)        {            if(!visited[i])            {                dfs(i, i);            }        }        int fail = 0;        FOR(i, bad_edges.size())        {            int v = bad_edges[i].fi;            int u = bad_edges[i].se;            if(cc[v] == cc[u])            {                fail = 1;                break;            }        }        if(fail) cout << "NO" << endl;        else cout << "YES" << endl;    }    return 0;}`

### Second solution

`#include<bits/stdc++.h>using namespace std;int tests;string st[1<<20];int a[1<<20];int n,m,w[1<<20];int b[1<<20];int er;int get(int x){  if (x==w[x])    return x;  return w[x]=get(w[x]);}void merge(int a,int b){  a=get(a);  b=get(b);  w[a]=b;}int main(){ios_base::sync_with_stdio(0);cin>>tests;for (;tests;--tests){  cin>>n>>m;    for (int i=1;i<=n;i++)    w[i]=i;  for (int i=1;i<=m;i++)  {    cin>>a[i]>>st[i]>>b[i];    if (st[i]=="=")      merge(a[i],b[i]);  }  er=0;  for (int i=1;i<=m;i++)  {    if (st[i]=="=")      continue;    if (get(a[i])==get(b[i]))      er=1;  }  if (er)    cout<<"NO"<<endl;  else    cout<<"YES"<<endl;}return 0;}`