UVA 793 – Network Connections

March 9, 2023April 7, 2023Arunima Mandal 1 Comment

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

Note: This problem is a straightforward Union Find problem but one might struggle with the input criteria; almost like UVA 459. Please make sure you understand the concepts of taking string/character input in C++.

And 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.

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;
//    getchar(); //Taking one blank line
//    getchar();
//    cin.ignore();
//    cin.ignore(); //can use this instead of getchar();

    while(t--)
    {
        int node;
        cin>>node;

        vector<int> root(node+1), ranking(node+1);
        for(int i=0; i<node; i++)
        {
            root[i]=i;
            ranking[i]=1;
        }

        string s;
        int yes=0, no=0;

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

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

            if(ch=='c') Union(x, y, root, ranking);
            else
            {
                if(Find(x, root)==Find(y, root)) yes++;
                else no++;
            }
        }

        cout<<yes<<","<<no<<endl;
        if(t) cout<<endl;
    }
    return 0;
}

UVA 459 – Graph Connectivity

March 9, 2023April 7, 2023Arunima Mandal 2 Comments

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

Note: This problem is a straightforward Union Find problem but one might struggle with the input format. Please make sure you understand the concepts of taking string/character input in C++.

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--)
    {
        string s;
        char ch;
        cin>>ch;
        
        int node=ch-'A' + 1;
        vector<int> root(node),ranking(node);
        for(int i=0; i<node; i++)
        {
            root[i]=i;
            ranking[i]=1;
        }
        
        getchar(); //Flushig the '\n' character from the input buffer which was there for using cin
        while(getline(cin,s) && s.size())
        {
            int x=s[0]-'A';
            int y=s[1]-'A';
            Union(x, y, root, ranking);
        }
        int ans=0;
        for(int i=0; i<node; i++)
        {
            if(root[i]==i) ans++;
        }
        cout<<ans<<endl;
        if(t) cout<<endl;
    }
    return 0;
}

Prim’s Algorithm – Minimum Spanning Tree (MST)

February 25, 2023February 25, 2023Arunima Mandal Leave a comment

Note:

It’s a greedy approach. Basically, there are 3 steps in Krushkal’s algorithm.

Build an adjacency matrix
Select a random node to start with and push that to the priority queue(ascending ordered value.)
Do this until the number of nodes added to the MST list is less than the total number of nodes n:
- For each top() of the priority queue, check whether the node has already been considered for the MST list, if not then do:
  - Add that node to the MST list (marked visited)
  - Add the cost(surely it will be the lowest value possible in the priority queue) of the edge to the answer
  - Push all the adjacent nodes of that node to the priority queue to determine which node to add next.

Time Complexity:

O(ElogV) where E is the number of edges and V is the number of nodes.

Code:

#include <bits/stdc++.h>

using namespace std;

int Prims(vector<vector<pair<int, int> > > &edges, int n)
{
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > >pq;
    int vis[1003]= {0};
    int ans=0;
    int nodes_added=0;
    pq.push({0,0});
    while(nodes_added<n)
    {
        int cost=pq.top().first;
        int node=pq.top().second;
        pq.pop();
        if(!vis[node])
        {
            nodes_added++;
            vis[node]=1; //added to MST
            ans+=cost;
            for(int i=0; i<edges[node].size(); i++)
            {
                pq.push(edges[node][i]);
            }
        }
    }
    return ans;
}

int main()
{
    int n,m;
    cout<<"Enter the no. of nodes in the graph: ";
    cin>>n;
    cout<<"Enter the no. of edges: ";
    cin>>m;
    vector<vector<pair<int, int> > > edges(n);
    cout<<"Enter the and their corresponding cost (node node cost):"<<endl;
    for(int i=0; i<m; i++) //Building adjacency graph
    {
        int x,y,cost;
        cin>>x>>y>>cost;
        edges[x].push_back({cost, y});
        edges[y].push_back({cost, x});
    }
    int ans=Prims(edges, n);
    cout<<"The minimum cost for traversing all the nodes once: "<<ans<<endl;
    return 0;
}
/*
Sample input:
5
7
0 1 1
0 2 2
0 3 3
1 2 2
2 3 3
3 4 4
4 0 5

Sample Output:
10

Note: Minimum spanning tree formed by nodes 0-1-2-3-4

*/

Krushkal’s algorithm – Minimum Spanning Tree (MST)

February 23, 2023February 25, 2023Arunima Mandal Leave a comment

Note:

It’s a greedy approach. Basically, there are 3 steps in Krushkal’s algorithm.

Sort the edges according to their cost in ascending order.
Traverse through the sorted edges list upto n-1 length
- a.If the edge creates a loop(use Find or Union of Union-Find to check the loop), do not consider it.
- b. else add it to the MST list by using Union and add the cost of the edge to the answer.

Time Complexity:

O(ElogE) where E is the number of edges.

Code:

#include <bits/stdc++.h>

using namespace std;

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

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

int Krushkals(vector<vector<int>> &edges, int n)
{
    sort(edges.begin(), edges.end());
    vector<int> root(n+1);
    vector<int> rankk(n+1);
    for(int i=0; i<n; i++)
    {
        root[i]=i;
        rankk[i]=1;
    }
    int ans=0, groups=0;
    for(int i=0; i<edges.size() && groups<n-1; i++)
    {
        int x=edges[i][1];
        int y=edges[i][2];
        int cost=edges[i][0];
        if(Find(x, root)!=Find(y, root)) //if no cycle exists
        {
            Union(x,y,root, rankk);
            ans+=cost;
            groups++;
        }
    }
    return ans;

}

int main()
{
    int n,m;
    vector<vector<int> > edges;
    cout<<"Enter the no. of nodes in the graph: ";
    cin>>n;
    cout<<"Enter the no. of edges: ";
    cin>>m;
    cout<<"Enter the and their corresponding cost (node node cost):"<<endl;
    for(int i=0; i<m; i++)
    {
        int x,y,cost;
        cin>>x>>y>>cost;
        edges.push_back({cost, x, y});
    }
    int ans=Krushkals(edges, n);
    cout<<"The minimum cost for traversing all the nodes once: "<<ans<<endl;
    return 0;
}
/*
Sample input:
5
7
0 1 1
0 2 2
0 3 3
1 2 2
2 3 3
3 4 4
4 0 5

Sample Output:
10

Note: Minimum spanning tree formed by nodes 0-1-2-3-4

*/

Disjoint Set/ Union Find (Union by Rank + Path Compression)

February 22, 2023April 7, 2023Arunima Mandal 2 Comments

Note:

**Must practice the problems mentioned at the end of this post to fully grasp this algorithm.

There can be many ways one can write the Union() and the Find() functions. I have written two approaches to do the Union functions here. Both of them are the most optimized. Both of them are based on the Quick Union algorithm implemented with the two optimizing techniques called Union by Rank and Path Compression. But the difference is just how I am doing the Union by Rank, that is how I am updating the ranking vector inside the Union() function.

In the first one – Union_ranking_by_total_connected_nodes(), the ranking vector is updated each time with the ranking of the other root node it is being connected to. That is, at the end of calling the Union() function for each pair of nodes to be connected, the ranking vector will contain the total number of connected nodes to each node.

In the second one – Union_ranking_by_height(), I use the least possible value in the ranking[] vector. That is, I increase the ranking of the root when both rankings are equal. Otherwise, I just don’t increase the ranking since we are already pushing the lower-valued ranking of a node to a higher-valued one. That is the higher-valued one would remain higher-valued or will be equal to the other now. But in the case of comparison, the comparison result will remain the same. In summary, the ranking vector here contains the “height” of each node.

You can use any one of them. I prefer the first one as that can be quite handy while solving many related problems.

Code:

#include <bits/stdc++.h>

using namespace std;

int Find(int x, vector<int> &root) //O(alpha(N)) //O(1)
{
    if(root[x]==x) return x;
    return root[x]=Find(root[x],root); //Path compression
}

/// Use any one of the following two - maybe rename as Union() 

//ranking_by_total_connected_nodes
void Union_ranking_by_total_connected_nodes(int x, int y, vector<int> &root, vector<int> &ranking) //O(alpha(N)) //O(1) 
{
    int rootX=Find(x, root);
    int rootY=Find(y, root);
    if(rootX!=rootY) //Union by Rank
    {
        if(ranking[rootX]>ranking[rootY]) root[rootY]=rootX;
        else if(ranking[rootY]>ranking[rootX]) root[rootX]=rootY;
        else
        {
            root[rootY]=rootX;
            ranking[rootX]++;
        }
    }
}

//ranking_by_height
void Union_ranking_by_height(int x, int y, vector<int> &root, vector<int> &ranking) //O(alpha(N)) //O(1)
{
    int rootX=Find(x, root);
    int rootY=Find(y, root);
    if(rootX!=rootY) //Union by Rank
    {
        if(ranking[rootX]>ranking[rootY]) root[rootY]=rootX;
        else if(ranking[rootY]>ranking[rootX]) root[rootX]=rootY;
        else
        {
            root[rootY]=rootX;
            ranking[rootX]++;
        }
    }
}

bool unionFind(int x, int y, vector<int> &root)
{
    return Find(x, root)==Find(y, root);
}

int main()
{
    int n,m;
    cout<<"Enter the number of nodes: ";
    cin>>n;
    //Initially all nodes are independent
    vector<int> root(n+1), ranking(n+1);//will be (n) if indexing of nodes starts from 0
    for(int i=1; i<=n; i++)//will be (i=0; i<n;..) if indexing of nodes starts from 0
    {
        root[i]=i;
        ranking[i]=1;
    }

    cout<<"Enter the number of connections: "<<endl;
    cin>>m;
    cout<<"Enter the connections i.e. two nodes wo are connected"<<endl;
    for(int i=0; i<m; i++)
    {
        int x, y;
        cin>>x>>y;
        Union_ranking_by_total_connected_nodes(x, y, root, ranking);
        /*
        cout<<"####Root vector#####"<<endl;
        for(int i=1; i<=n; i++)
        {
            cout<<i<<" "<<root[i]<<endl;
        }
        */
    }

    cout<<"#######################"<<endl;
    int ans=0;
    for(int i=1; i<=n; i++)//will be (i=0; i<n;..) if indexing of nodes starts from 0
    {
        if(root[i]==i) ans++;
    }
    cout<<"There are "<<ans<<" different connected components"<<endl;

    cout<<"#######################"<<endl;
    int q;
    cout<<"Enter the number of queries: "<<endl;
    cin>>q;
    cout<<"Enter the nodes whose connections you want to check: "<<endl;
    for(int i=0; i<q; i++)
    {
        int x, y;
        cin>>x>>y;
        bool ans=unionFind(x, y, root);
        if(ans==1) cout<<"Connected!"<<endl;
        else cout<<"Not connected"<<endl;
    }
    return 0;
}
// Input: 1 2-3-4-5-8-9-10  6 7
/*
10
6
2 3
3 4
3 5
8 9
9 10
5 10
*/
//Output
/*
#######################
There are 4 different connected components
#######################
Enter the number of queries:
...
*/

**One important thing to observe here is – after connecting all the connected nodes using the Union function, the root vector does not contain all the actual root nodes of the other nodes! That is most of the nodes are having the actual root (as ensured by the Find() function that is called at the beginning of the Union() ), but some node’s actual roots are not updated yet, instead, in the root vector, they are containing their parent node may be.

The reason is: Remember that at the beginning of the Union function, we are updating root nodes while calling the Find function for each of the two nodes. But then we are leaving the Union function by just updating the parent nodes’ root of Y (root[rootY]=rootX). We are not doing root[y]=rootX (Please see the code below for the reference of x, y, rootX, rootY).

So after using the function Union to connect all the connected nodes, to get any nodes root node, say for a node called z, we’ll have to use the Find function, or we can just check the root vector and go through it until we find the root node using this – while(z!=root[z]) {z=root[z]; return z;}. Now z is the root node.

Time Complexity:

Each module – Union, Fnd, and UnionFind are O(α(N)). Here α is the Inverse Ackermann function. In practice, we assume it’s a constant. In other words, O(α(N)) is regarded as O(1) on average.

So the overall time complexity is O(N) if those are called N times.

Related Problems to solve (Sorted according to the INCREASING difficulty level):

Must do problems 1, 5 & 8 to understand the algorithm fully. These 3 problems cover every aspect of the Union-Find algorithm. Other problems are mainly about manipulating the input to feed to the basic Union-Find algorithm.

Fall out, Codes!

Let all the problems bow before your patience and stubbornness!

Category UVa

UVA 793 – Network Connections

UVA 459 – Graph Connectivity

Prim’s Algorithm – Minimum Spanning Tree (MST)

Krushkal’s algorithm – Minimum Spanning Tree (MST)

Disjoint Set/ Union Find (Union by Rank + Path Compression)