Category Topsort

UVa – 200 – Rare Order

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/2/200.pdf

Note: I think the problem statement was very much unclear. The important thing to notice is that it is explicitly mentioned in the input section that the string will be ordered. So you cannot change the order of the string.

Now, the problem actually demands printing unique characters column wise maintaining that each character you are printing cannot be printed twice. So simply put – “print unique characters of the ordered strings by column-wise traversal”.

For example, for the input:

XYZ

ZUX

XWV

#

So in the 1st column, there are XZX, where X is repeated, so we get XZ from this column.

in the 2nd column, there is YUW, where no character was found before, all are new, so we get YUW from this column.

In the 3rd column, there are ZXZ, here both X and Z already exist in our finding, only V is new, so we get V from this column.

At the end of the traversal, by concatenating all column’s results, we have XZYUWV – which is the output.

I have solved this using the above brute force method, so no DFS or Topological Sort is needed here if time is a concern.

**We’ll have to keep in mind that, all string sizes may not be the same. So we’ll have to take care of that while traversing and accessing elements.

**For the first time, the output of UDebug’s test cases’ output didn’t match up with mine (but this code was accepted by the UVa) which means that the UDebug test cases are wrong because the output was supposed to be unique as per my understanding. If that is not the case not, please let me know in the comments. Thanks!

Code:

#include <bits/stdc++.h>

using namespace std;

int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    vector<string> v;
    int maxi=INT_MIN;
    string s;
    while(cin>>s)
    {
        if(s!="#")
        {
            v.push_back(s);
            maxi=(maxi, s.size());
        }
        else
        {
            unordered_map<char,int> visited;
            for(int j=0; j<maxi; j++)
            {
                for(int i=0; i<v.size(); i++)
                {
                    string ss=v[i];
                    if(j<ss.size() && !visited.count(ss[j]))
                    {
                        cout<<ss[j];
                        visited[ss[j]]=1;
                    }
                }
            }
            cout<<endl;
            v.clear();
            maxi=INT_MIN;
        }
    }
    return 0;
}

UVa – 11060 – Beverages

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/110/11060.pdf

Note: This problem can be solved using basic topological sort but with a simple tweak to maintain the order required in the problem statement. I used a priority queue to maintain the ascending order of the nodes that have indegree 0.

Code:

#include <bits/stdc++.h>

using namespace std;


vector<int> topSort(int node, vector<int> &indeg, vector<vector<int> > &adj)
{
    vector<int> ans;
    priority_queue<int, vector<int>,  greater<int > > pq;

    for(int i=0; i<node; i++)
    {
        if(indeg[i]==0) pq.push(i);
    }

    while(!pq.empty())
    {
        int u=pq.top();
        pq.pop();
        ans.push_back(u);
        for(int j=0; j<adj[u].size(); j++)
        {
            int v=adj[u][j];
            indeg[v]--;
            if(indeg[v]==0) pq.push(v);
        }
    }
    return ans;
}


int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    int z=1;
    int node,edge;
    while(cin>>node)
    {
        unordered_map<string,int> mp1;
        unordered_map<int,string> mp2;
        int c=0;
        for(int i=0; i<node; i++)
        {
            string s;
            cin>>s;
            mp1[s]=c;
            mp2[c]=s;
            c++;
        }

        cin>>edge;
        vector<vector<int> > adj(node);
        vector<int> indeg(node,0);

        for(int i=0; i<edge; i++)
        {
            string from,to;
            cin>>from>>to;
            adj[mp1[from]].push_back(mp1[to]);
            indeg[mp1[to]]++;
        }

        vector<int> ans=topSort(node, indeg, adj);

        cout<<"Case #"<<z<<": Dilbert should drink beverages in this order:";

        for(int i=0; i<ans.size(); i++)
        {
            cout<<" "<<mp2[ans[i]];
        }
        cout<<"."<<endl<<endl;
        z++;
    }
    return 0;
}

LeetCode 2115. Find All Possible Recipes from Given Supplies

Arunima Mandal Leave a comment

Problem Link: https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/description/

Note: Since the problem explicitly demands dependency, and the recipes are the ultimate nodes that have indegrees topological sort is the most intuitive thing that can come to mind if you know the idea of the topological sort well. I used Kahn’s algorithm here to do the topological sort.

  • Time complexity: O(n)
  • Space complexity: O(n)
class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_map<string, vector<string> > ump;
        unordered_map<string,int> indegree;
        vector<string> ans;
        for(int i=0; i<ingredients.size(); i++)
        {
            for(int j=0; j<ingredients[i].size(); j++)
            {
                 ump[ingredients[i][j]].push_back(recipes[i]);
                 indegree[recipes[i]]++;
            }
        }
        for(int i=0; i<supplies.size(); i++)
        {   
            for(int j=0; j<ump[supplies[i]].size(); j++)
            {
                string adj=ump[supplies[i]][j];
                indegree[adj]--;
                if(indegree[adj]==0)
                {
                    supplies.push_back(adj);
                    ans.push_back(adj);
                }
            }
        }
        return ans;
    }
};

Topological Sorting: Kahn’s algorithm

Arunima Mandal Leave a comment

This algorithm requires no Queue or Stack.

#include <bits/stdc++.h>
#define MAX  2000

using namespace std;

vector<int> topSort(int node, vector<int> &indeg, vector<vector<int> > &adj)
{
    vector<int> ans;
    for(int i=0; i<node; i++) //Inserting all independent nodes first
    {
        if(indeg[i]==0) ans.push_back(i);
    }

    for(int i=0; i<ans.size(); i++)
    {
        int u=ans[i];
        for(int j=0; j<adj[u].size(); j++)
        {
            int v=adj[u][j];
            indeg[v]--;
            if(indeg[v]==0) ans.push_back(v);
        }
    }
    if(ans.size()!=node) ans.clear(); //cycle found, so returning empty vector
    return ans;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int node, edge;
    cout<<"Enter the number of nodes and edges: ";

    while(cin>>node>>edge) //assuming node>=0, edges>=0
    {
        vector<int> indeg(node,0);
        vector<vector<int> > adj(node);
        /* //for string input
        unordered_map<string,int> mp;
        unordered_map<int,string> mp;
        int c=0;
        */

        if(edge==0) //Print all nodes as all are independent
        {
            for(int i=0; i<node; i++) cout<<i<<" ";
            cout<<endl;
        }

        cout<<"Enter the relations(pair of edges): "<<endl;

        for(int i=0; i<edge; i++) //Populating Adjacency list and indeg array for TopSort
        {
            int from,to;
            //string from,to;
            cin>>from>>to;

            /* //Processing string input

            if(mp1[from]==0)
            {
                mp1[from]=++c;
                mp2[c]=from;
            }
            if(mp1[to]==0)
            {
                mp1[to]=++c;
                mp2[c]=to;
            }
            g[mp1[from]].pb(mp1[to]);
            indeg[mp1[to]]++;
            */
            adj[from].push_back(to);
            indeg[to]++;
        }

        vector<int> ans=topSort(node, indeg, adj);

        if(ans.size()>0) //Ordering possible
        {
            cout<<"The correct ordering is:";
            for(int i=0; i<ans.size(); i++)
            {
                cout<<" "<<ans[i];
                //cout<<mp2[ans[i]]<<" ";
            }
            cout<<endl;
        }
        else cout<<"Cycle exists"<<endl; //Ordering not possible
    }
    return 0;
}

Light OJ-1003 – Drunk

Arunima Mandal Leave a comment 
#include <bits/stdc++.h>

#define ms(a,b)         memset(a,b,sizeof(a))
#define pb(a)           push_back(a)
#define db              double
#define ft              float
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define vc              vector
#define vi              vector<int>
#define vll             vector<long long>
#define pii             pair<int,int>
#define pis             pair<int,string>
#define psi             pair<string,int>
#define all(x)          x.begin(),x.end()
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n)      for(int i=0;i<n;i++)
#define loop1(i,n)      for(int i=1;i<=n;i++)
#define stlloop0(i,x)   for(int i=0;i<x.size();i++)
#define stlloop1(x)     for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)       __gcd(a, b)
#define lcm(a, b)       ((a)*((b)/gcd(a,b)))
#define PI              3.14159265358979323846264338328
#define MAX             10001

using namespace std;

vector<int>g[MAX],top;
int indeg[MAX];
map<string,int> mp;

int main()
{
     CIN;
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int t,m;
    cin>>t;
    loop1(z,t)
    {
        cin>>m;
        int c=1;
        ms(indeg,0);
        for(int i=0; i<m; i++)
        {
            string from,to;
            cin>>from>>to;
            if(mp[from]==0)
            {
                mp[from]=c;
                c++;
            }
            if(mp[to]==0)
            {
                mp[to]=c;
                c++;
            }
            g[mp[from]].pb(mp[to]);
            indeg[mp[to]]++;
        }
        for(int i=1; i<=c-1; i++)
        {
            if(indeg[i]==0) top.pb(i);
        }
        for(int i=0; i<top.size(); i++)
        {
            int v=top[i];
            for(int j=0; j<g[v].size(); j++)
            {
                int u=g[v][j];
                indeg[u]--;
                if(indeg[u]==0) top.pb(u);
            }
        }
        if(top.size()==c-1) cout<<"Case "<<z<<": Yes"<<endl;
        else cout<<"Case "<<z<<": No"<<endl;
        loop0(i,MAX) g[i].clear();
        top.clear();
        mp.clear();
    }
    return 0;
}