UVA – 10227 – Forests

Arunima Mandal

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

One thought on “UVA – 10227 – Forests”

  1. Pingback: Disjoint Set/ Union Find (Union by Rank + Path Compression) | Fall out, Codes!

Leave a comment