Problem Link: https://onlinejudge.org/external/101/10158.pdf

Note:

This problem is an interesting application of the Disjoint-Set algorithm! Though it might seem puzzling at first, especially the Enemy relations, the main thing to understand is we’ll need to keep all the relations in one tree.

While approaching the problem, it feels like, we can have two trees, one for Friend relations and another for Enemy relations. And we can build each tree and check each tree separately according to the value of c. But this approach becomes infeasible as this problem is considering the real-world scenario of the Enemy relations(symmetric and irreflexive – as mentioned in the problem statement).

If this problem was not considering the real-world scenario of enemies (like an enemy of my friend is my enemy, Or an enemy of my enemy is my friend), that is if the Enemy relations were also equivalence relations just like Friend relations, then we could have taken the above approach. But as that is not the case, so we’ll have to think of other approaches.

The key point is, we’ll have to use the Disjoint-set, and there will be no change in the main algorithms. All we need to do is to tweak the input and feed that to the Union-Find algorithm(Disjoint-Set) to form and search in only one tree.

Since we need one tree, let us keep the Friends input as it is, and take the Enemy input as n+x where n is the number of people and x is the ith people (0 <= i < n). See here we are modifying the input such that it doesn’t mess up with our main input. So think like this – we are assigning all the numbers from o to n-1 as the Friend’s world and from n to n+n-1 as the Enemy’s world. All the Unions we will create now, will not be whether they are connected as friends or enemies, they will be just connected as relations in the tree. In the main function, we’ll have to determine, if the relation is a friend or an enemy.

From now onward, I am considering two inputs x and y. So the Friend’s relation will be the same- Union(x,y). But we need to do Union(enemyID(x), enemyID(y)) because, since this is the same tree and we keep tracking of relations only in the tree, if we make a friend (2,3) and again attempt to make (2,3) enemy, then the tree will only show that 2 and 3 are connected(the tree doesn’t know whether they are friend or enemy), but we should now print “-1” as they are already a friend. That’s why we need to do the Union(enemyID(x), enemyID(y)) in the sense that, in the enemy world they are also connected but as friends.

Similarly, we are marking enemies by Union(x, enemyID(y)) and Union(y, enemyID(x)) to establish relations in the tree and mark the relationship as an enemy in the main function.

My takeaway from this problem is:

1. Make separate(exclusive) worlds necessary in the main function so that in 1 tree we can keep all the relations.
2. Create and determine the relations in the main function, not in the tree. The tree would only contain any relations.

This seems like a complex solution but with practice, the more problems we solve, the more this type of idea of manipulating inputs will come to our mind.

Code:

#include <bits/stdc++.h>

using namespace std;

int Find(int x, vector<int> &root)
{
    if(x==root[x]) return x;
    return root[x]=Find(root[x], root);
}

void Union(int x, int y, vector<int> &root, vector<int> &ranking)
{
    int rootX=Find(x, root);
    int rootY=Find(y, root);
    if(rootX!=rootY)
    {
        if(ranking[rootX]>=ranking[rootY])
        {
            root[rootY]=rootX;
            ranking[rootX]+=ranking[rootY];
        }
        else
        {
            root[rootX]=rootY;
            ranking[rootY]+=ranking[rootX];
        }
    }
}

int enemyID(int x, int n)
{
    return n+x;
}

int main()
{
    int n, c, x, y;
    while(cin>>n)
    {
        vector<int> root(n+n), ranking(n+n);
        for(int i=0; i<(n+n); i++)
        {
            root[i]=i;
            ranking[i]=1;
        }
        while(cin>>c>>x>>y)
        {
            if(c==0) break;

            if(c==1)
            {
                if(Find(x, root)==Find(enemyID(y,n), root) || Find(y, root)==Find(enemyID(x,n), root))
                    cout<<"-1"<<endl;
                else
                {
                    Union(x, y, root, ranking);
                    Union(enemyID(x,n), enemyID(y,n), root, ranking);
                }
            }
            else if(c==2)
            {
                if(Find(x, root)==Find(y, root) || Find(enemyID(x,n), root)==Find(enemyID(y,n), root))
                    cout<<"-1"<<endl;
                else
                {
                    Union(x, enemyID(y,n), root, ranking);
                    Union(y, enemyID(x,n), root, ranking);
                }
            }
            else if(c==3)
            {
                if(Find(x, root)==Find(y, root) || Find(enemyID(x,n), root)==Find(enemyID(y,n), root))
                    cout<<"1"<<endl;
                else cout<<"0"<<endl;
            }
            else if(c==4)
            {
                if(Find(x, root)==Find(enemyID(y,n), root) || Find(y, root)==Find(enemyID(x,n), root))
                    cout<<"1"<<endl;
                else cout<<"0"<<endl;
            }
        }

    }
    return 0;
}