990. Satisfiability of Equality Equations | LeetCode Solution | DSU

You are given an array of strings `equations` that represent relationships between variables where each string `equations[i]` is of length `4` and takes one of two different forms: `"xi==yi"` or `"xi!=yi"`.Here, `xi` and `yi` are lowercase letters (not necessarily different) that represent one-letter variable names.

Return `true` if it is possible to assign integers to variable names so as to satisfy all the given equations, or `false` otherwise.

Example 1:

`Input: equations = ["a==b","b!=a"]`
`Output: false`
```Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.
There is no way to assign the variables to satisfy both equations.
```

Example 2:

`Input: equations = ["b==a","a==b"]`
`Output: true`
```Explanation: We could assign a = 1 and b = 1 to satisfy both equations.
```

Constraints:

• `1 <= equations.length <= 500`
• `equations[i].length == 4`
• `equations[i][0]` is a lowercase letter.
• `equations[i][1]` is either `'='` or `'!'`.
• `equations[i][2]` is `'='`.
• `equations[i][3]` is a lowercase letter.
Solution:
We will make DSU and the parent array will have a size of 26 as of the English characters. If the current equation is of '==' then we will merge the two character else we will check in the next loop whether both the character has the same leader or parent. See the code for a better understanding.

1. /******************************************************************************

Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include
using namespace std;

int main() {
vector orderofreq ;
int pos;
int mx=INT_MAX;
vector::iterator nextreq ;
cout<<"No of requests in queue : ";
int n;
cin>>n; //No of requests
for(int i = 0; i < n; i++)
{
cin>>pos;
orderofreq.push_back(pos);
}

while(n--)
{

for(auto it = orderofreq.begin(); it != orderofreq.end(); it++)
{
{nextreq = it;
}
}
cout<<*nextreq<<" ";
mx=INT_MAX;
orderofreq.erase(nextreq);
}

return 0;
}

2. /******************************************************************************

Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

// Online C++ compiler to run C++ program online
#include
using namespace std;

int main() {
vector orderofreq ;
int pos;
int totalseektime = 0;
cout<<"No of requests in queue : ";
int n;
cin>>n; //No of requests
for(int i = 0; i < n; i++)
{
cin>>pos;
orderofreq.push_back(pos);
}

for(auto it: orderofreq)
{
}

cout<<"Total Seek Time is : "<<totalseektime;

return 0;
}

3. /******************************************************************************

Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include
using namespace std;

int main() {
vector orderofreq ;
int pos;
cout<<"No of requests in queue : ";
int n;
cin>>n; //No of requests
for(int i = 0; i < n; i++)
{
cin>>pos;
orderofreq.push_back(pos);
}

sort(orderofreq.begin(),orderofreq.end());
vector::iterator itr;

for(auto it = orderofreq.begin(); it != orderofreq.end(); it++)
{
{
itr = it;
break;
}
}
for(auto it = itr; it != orderofreq.end(); it++)
{
}
itr--;
for(auto it = itr; it != orderofreq.begin(); it--)
{
}

return 0;
}

4. //C-Scan
#include
using namespace std;

int main() {
int rwarm,n,nextarm,rwarmpos;

cout<<"Enter the position of read/write arm :";
cin>>rwarm;
rwarmpos = rwarm;
cout<<"Enter the number of requests : ";
cin>>n;
vector req;
for(int i = 0; i < n; i++)
{cin>>nextarm;
req.push_back(nextarm);
}

nextarm = rwarm;
sort(req.begin(),req.end());

auto itr = req.begin();

for(auto it = req.begin(); it != req.end(); it++)
{
if(rwarm<*it)
{
itr = it;
break;
}
}

for(auto it = itr; it != req.end(); it++)
{
nextarm = *it;
rwarm = nextarm;
}

if(nextarm < 199) totalheadmov += (199 - nextarm);

rwarm = 0;
nextarm = req[0];

int it = 0;

while(nextarm < rwarmpos)
{
rwarm = nextarm;
nextarm = req[++it];
}

return 0;
}

5. //SCAN
#include
using namespace std;

int main() {
int rwarm,n,nextarm,rwarmpos;

cout<<"Enter the position of read/write arm :";
cin>>rwarm;
rwarmpos = rwarm;
cout<<"Enter the number of requests : ";
cin>>n;
vector req;
for(int i = 0; i < n; i++)
{cin>>nextarm;
req.push_back(nextarm);
}

nextarm = rwarm;
sort(req.begin(),req.end());

auto itr = req.begin();

for(auto it = req.begin(); it != req.end(); it++)
{
if(rwarm<*it)
{
itr = it;
break;
}
}

for(auto it = itr; it != req.end(); it++)
{
nextarm = *it;