Category Disjoint Set / Union Find

UVa – 11690 – Money Matters

Arunima Mandal 1 Comment

Problem Link: https://onlinejudge.org/external/116/11690.pdf

Note: This is a slight variation of the problem UVa – 10608 – Friends. Aside from figuring out that we need each node’s actual root (to determine each separate collection) as in the UVa 10608, we need to figure out how to calculate the money owes and money owed.

Ultimately, people in the same group or collection can make an exchange with one another. For example, for the test case,

4 2 //n=4, m=2
15
20
-10
-25
0 2
1 3
1 2

So initially, money_owe[]={15, 20, -10, -25}

Here, for Union(0, 2), 0 can give money to 2, then money_owe[] would be: money_owe[]={5, 20, 0, -25}.

Then for(1, 3), 1 can give money to 3, then money_owe[] would be: money_owe[]={5, 0, 0, -5}.

Here, for Union(1, 2), 1 can give money to 2, then money_owe[] would be: money_owe[]={5, 0, 0, -5}.

Notice that, for the last pair, nothing changes as none of them owes or is owed money. But just for this pair, each of the people has become 1 single group. Without this pair, the output of the problem would be “IMPOSSIBLE”. But since our example input has this pair, so all people are Friends, so they can share money. Hence, person 0 and person 3 can exchange money even though they are not directly connected.

In summary, we just need to check every group’s total sum. If the sum for any single group is not equal to 0, then we can immediately say that it is IMPOSSIBLE.

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 n,m;
        cin>>n>>m;

        vector<int> root(n), ranking(n);
        int money_owe[n];

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

            int money;
            cin>>money;
            money_owe[i]=money;
        }

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

        vector<vector<int> > members(n);
        for(int i=0; i<n; i++)
        {
              int root_i=Find(i, root);  //updating the final root vector
              members[root_i].push_back(i);
        }
        bool f;
        for(int i=0; i<n; i++)
        {
            int sum=0;
            for(int j=0; j<members[i].size(); j++)
            {
                sum+=money_owe[members[i][j]]; // the sum of money should be 0 within a group
            }

            f=0;
            if(sum!=0)
            {
                cout<<"IMPOSSIBLE"<<endl;
                f=1;
                break;
            }
        }
        if(!f)cout<<"POSSIBLE"<<endl;
    }
    return 0;
}

UVa – 10685 – Nature

Arunima Mandal 1 Comment

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

Note: This problem is the basic application of the Union-Find algorithm. With the slight input manipulation, it is actually pretty similar to the problem UVa – 10608 – Friends. Just like that problem, this problem can be solved with approach 2 mentioned in the “Friends” problem, but I prefer approach 1.

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;
    while(cin>>n>>m)
    {
        if(n==0 && m==0) break;

        vector<int> root(n), ranking(n);
        unordered_map<string,int> ump;
        int c=0;
        for(int i=0; i<n; i++)
        {
            root[i]=i;
            ranking[i]=1;

            string s;
            cin>>s;
            ump[s]=c;
            c++;
        }

        for(int i=0; i<m; i++)
        {
            string s1, s2;
            cin>>s1>>s2;
            Union(ump[s1], ump[s2], root, ranking);
        }

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

UVa – 11966 – Galactic Bonding

Arunima Mandal 1 Comment

Problem Link: https://onlinejudge.org/external/119/11966.pdf

Note: This problem is the basic implementation of the Union-Find problem.

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;
    for(int z=1; z<=t; z++)
    {
        int n;
        double d;
        cin>>n>>d;
        vector<int> root(n), ranking(n);

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

        vector<pair<double, double> > v;
        for(int i=0; i<n; i++)
        {
            double x,y;
            cin>>x>>y;
            v.push_back({x,y});
        }

        for(int i=0; i<n-1; i++)
        {
            double x1=v[i].first;
            double y1=v[i].second;
            for(int j=i+1; j<n; j++)
            {
                double x2=v[j].first;
                double y2=v[j].second;
                double dis=sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)); //General formula of distance between two points on a 2D plane
                if(dis<=d) Union(i, j , root, ranking);
            }
        }

        int ans=0;
        for(int i=0; i<n; i++)
        {
            if(root[i]==i) ans++;
        }
        cout<<"Case "<<z<<": "<<ans<<endl;
    }
    return 0;
}

UVa – 11503 – Virtual Friends

Arunima Mandal 1 Comment

Problem Link: https://onlinejudge.org/external/115/11503.pdf

Note: This is another problem that is basically using the “ranking” property of the Union-Find algorithm.

Since the ranking vector of this code basically contains the “number of total nodes” connected to the root node at any time we are calling the Union() function, just returning that value whenever we are calling the Union() function will be our desired answer.

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

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

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

        for(int i=0; i<100005; i++)
        {
            root[i]=i;
            ranking[i]=1;
        }
        unordered_map<string, int> ump;
        int c=0;
        for(int i=0; i<m; i++)
        {
            string s1,s2;
            cin>>s1>>s2;
            if(!ump.count(s1))
            {
                ump[s1]=c;
                c++;
            }
            if(!ump.count(s2))
            {
                ump[s2]=c;
                c++;
            }
            cout<<Union(ump[s1],ump[s2], root, ranking)<<endl;
        }
    }
    return 0;
}

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