Category UVa

UVa – 10608 – Friends

Arunima Mandal 3 Comments

Problem Link: https://onlinejudge.org/external/106/10608.pdf

Approach 1: This code is simply using the ranking vector of the Union-Find algorithm when we update the ranking vector by the total number of connected nodes to the root node.

#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 main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        vector<int> root(n+1), ranking(n+1);

        for(int i=1; i<=n; i++)
        {
            root[i]=i;
            ranking[i]=1;
        }

        for(int i=0; i<m; i++)
        {
            int x,y;
            cin>>x>>y;
            Union(x,y, root, ranking);
        }

        int ans=-1;
        for(int i=1; i<=n; i++)
        {
            ans=max(ranking[i], ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}

Approach 2: If the ranking vector is updated by the height of the node, then we’ll have to do something extra in the main function to get the answer to this problem. This is exactly why I prefer the first approach though both of these approaches have the same time complexity.

Here, after establishing the relationship between all the pairs of people, we are implementing the Find function for each of the people. Because as I mentioned in the basic algorithm discussion – here(the “important observation”), after using the Union function for all pairs, our root vector is not fully updated yet.

That’s why we need to run Find() function for each of the nodes to get the actual root node of all the nodes. And in the meantime, we are collecting the number of nodes each root node is containing including itself.

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;
        else if(ranking[rootY]>ranking[rootX]) root[rootX]=rootY;
        else
        {
            root[rootY]=rootX;
            ranking[rootX]++;
        }
    }
}

int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        vector<int> root(n+1), ranking(n+1);

        for(int i=1; i<=n; i++)
        {
            root[i]=i;
            ranking[i]=1;
        }

        for(int i=0; i<m; i++)
        {
            int x,y;
            cin>>x>>y;
            Union(x,y, root, ranking);
        }

        int member_count[n+1]={0};
        for(int i=1; i<=n; i++)
        {
              int root_i=Find(i, root);  //updating the final root vector
              member_count[root_i]++;
        }

        int ans=-1;
        for(int i=1; i<=n; i++)
        {
            ans=max(member_count[i], ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}

UVa – 10583 – Ubiquitous Religions

Arunima Mandal 1 Comment

Problem Link: https://onlinejudge.org/external/105/10583.pdf

Note: This is a straightforward application of the Union-Find(Disjoint Set) algorithm.

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 main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int n,m, t=1;
    while(cin>>n>>m)
    {
        if(n==0 && m==0) break;
        vector<int> root(n+1), ranking(n+1);
        for(int i=1; i<=n; i++)
        {
            root[i]=i;
            ranking[i]=1;
        }
        for(int i=0; i<m; i++)
        {
            int x,y;
            cin>>x>>y;
            Union(x,y, root, ranking);
        }
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            if(root[i]==i) ans++;
        }
        cout<<"Case "<<t<<": "<<ans<<endl;
        t++;
    }
    return 0;
}

UVA – 10158 – War

Arunima Mandal 1 Comment

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

UVA – 10227 – Forests

Arunima Mandal 1 Comment

Problem Link: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&category=0&problem=1168

Note: This problem is a Disjoint set problem, but a tricky one indeed. Here the main concern is to understand the input, and what input will be fed to the Disjoint set algorithm. We’ll have to understand what the opinion means patiently and carefully.

About the input format, we do not have to bother with the blank lines because “std::cin” by nature isn’t bothered with those blank lines. We’ll just have to make sure that we use getchar() before using getline() as there are some “cin” statements before using getline(). Please have a look at the following link for further explanation.

The following code is basically the disjoint set algorithm + the “graph” vector and the two for loops inside the main function.

So the purpose of those is to make the feasible input to be fed to the disjoint set algorithm. Now, for the sample input that is given in the problem statement:

1

3 4
1 2
3 3
1 3
2 2
3 2
2 4

Explanation of the code with respect to the above input:

I have considered a vector of sets named graph, where I am keeping track of which person has heard which set of trees. After processing the input, before running the two for loops, the above input seems like:

graph[1]={2,3}

graph[2]={2,4}

graph[3]={2,3}

Then in the two for loops, if the two person’s set matches, then I am making those two people as “connected” via the “Union” function. And lastly checking which of the people are connected or not.

**My two cents on this problem: In such kinds of problems, the key to thinking intuitively is – Ultimately we need to find out which type of group has to be connected(to apply the Union function) and has to be checked whether they are connected or not.

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 main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int t;
    cin>>t;

    while(t--)
    {
        int people, trees;
        cin>>people>>trees;

        vector<set<int> > graph(people+1);
        vector<int> root(people+1), ranking(people+1);

        for(int i=1; i<=people; i++)
        {
            root[i]=i;
            ranking[i]=1;
        }
        string s;

        getchar(); //Flushig the '\n' from the input buffer which was there for using cin

        while(getline(cin,s) && s.size())
        {
            size_t found=s.find(" ");
            string num1=s.substr(0, found);
            int x=stoi(num1);
            string num2=s.substr(found+1);
            int y=stoi(num2);

            graph[x].insert(y);

        }

        for(int i=1; i<=graph.size(); i++)
        {
            for(int j=i+1; j<=graph.size(); j++)
            {
                if(graph[i]==graph[j]) Union(i, j, root, ranking);
            }
        }

        int ans=0;
        for(int i=1; i<=people; i++)
        {
            if(root[i]==i) ans++;
        }
        cout<<ans<<endl;
        if(t) cout<<endl;
    }
    return 0;
}

UVA – 10178 – Count the Faces

Arunima Mandal 1 Comment

Problem link: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1119

Note:

This problem mainly comprises one main concern – calculating the faces. Now there is already a famous formula – Euler’s formula for calculating the number of faces in a planar graph which is

{\displaystyle v-e+f=2.}

Here, v = total number of vertices of all the connected components of the planar graph

e = total number of edges of all the connected components of the planar graph

f = number of faces (regions bounded by edges, including the outer, infinitely large region) of the planar graph

Since we want the faces for this problem, the equation we should be looking for is:

f = 2 + e − v …………………………………………………………… (1)

Now, at this point it is seeming pretty easy to get the number of faces, right? Because we just need only the number of vertices and edges and nothing else!! But here goes the main concern – The above equation is assuming there is only one connected component in the planar graph. So if the overall graph is not connected, that means, if, in the plane, we are talking about multiple subgraphs that are disconnected from each other, then we’ll have to apply the above equation for each of the connected components to get the total number of faces, right?

But again, in that case (more than 1 connected component), there is another certain issue – the face counter for the outer region gets counted equal to the number of different connected component, which actually should be counted as 1.

For example: Suppose we are considering the below graphs as the input of our problem.

Here, in the plane, the number of connected components is 2 (A-B-C-D and E-F-G-H) and the above equation will generate the number of faces for each connected component as 2, so in total 4 faces for the graphs present in this plane. But the result should be 3 instead of 4.



So the thing is that, we should consider only 1 face for the enitre infinite outer region for all the different connected components. So the equation for our problem would be modified to:

f = ( e − v + number of connected components ) + 1 …………………………. (2)

This will be applicable because we can easily derive that, if we make summation of each connected component, then we can reach to the above equation for considering only 1 outer region for all the connected components present in the plane.

Now the solution to the problem comes down to the two following steps:

  1. Find out the number of connected components (/ number of cycles in the undirected graph) in the graph that is given to us
  2. Put that into the modified Euler’s equation (2) to get the result.

The first part of the solution can be solved in many different ways like DFS or Disjoint set. I have used the Disjoint set algorithm here.

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); //Path compression
}

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 main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int node, edge;
    while(cin>>node>>edge)
    {
        vector<int> root(node+1), ranking(node+1);
        for(int i=1; i<=node; i++)
        {
            root[i]=i;
            ranking[i]=1;
        }
        unordered_map<char, int> ump;
        int c=0;
        for(int i=0; i<edge; i++)
        {
            char a,b;
            cin>>a>>b;
            if(!ump.count(a))
            {
                c++;
                ump[a]=c;
            }
            if(!ump.count(b))
            {
                c++;
                ump[b]=c;
            }

            int x=ump[a];
            int y=ump[b];
            Union(x, y, root, ranking);
        }

        int faces=0;
        for(int i=1; i<=node; i++)
        {
            if(root[i]==i) faces++;
        }
        cout<<(edge-node+faces)+1<<endl; //the +1 is for 1 infinite outer region
    }
    return 0;
}