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


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