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