UVA – 10178 – Count the Faces

March 17, 2023March 30, 2023Arunima 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

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:

Find out the number of connected components (/ number of cycles in the undirected graph) in the graph that is given to us
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;
}

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

*/

Is vector<vector> costlier than vector<pairs> in C++?

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

Yes, it is way costlier! I stumbled on the problem very recently and got these two very useful links in Google. Please check these out for a thorough understanding.

The following link is helpful for core theoretical logic – https://stackoverflow.com/questions/73095254/how-is-vectorvectorint-heavier-than-vectorpairint-int
And here the fact is experimentally proved which is cool! – https://codeforces.com/blog/entry/110222

So my take on this is:

When we need a large vector size but a small number of walkthroughs, the vector<pair<int>> implementation has a way more advantage over vector<vector<int>>.
When you need larger walkthroughs per index of the outside vector(maybe you do not know even the actual size of the inside vector), then it is better to declare the vector with size and later assign values to it instead of pushing back (that’s given when you declare the size of the vector!) throughout the code.

For example,

a. vector<vector<int>> v (n, vector<int> (m,0)); – When you know the size of the inside vector – m

b. vector<vector<int>> v (n); (When you are not sure what the size of the inside vector would be)

Any of these two would give slightly better performance than just declaring vector<vector<int>> v;

Fall out, Codes!

Let all the problems bow before your patience and stubbornness!

Author Arunima Mandal

UVA – 10178 – Count the Faces

UVA 793 – Network Connections

UVA 459 – Graph Connectivity

Prim’s Algorithm – Minimum Spanning Tree (MST)

Is vector<vector> costlier than vector<pairs> in C++?