Category Graph

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

Iterative DFS for Detecting Cycle in any Directed Graph

Arunima Mandal Leave a comment

Note:

The algorithm for detecting cycles in any directed graph is easier using recursive DFS. But Iterative DFS approach to detect a cycle is a bit complex and tricky. I have commented on the code where necessary to make the algorithm more understandable.

In any case, the time complexity of the algorithm is O(V+E). 

#include <bits/stdc++.h>

using namespace std;

#define MAX 100005

bool detectCycle(int nodes, vector<vector<int> >& adjList)
{
    if(nodes==1) return false;
    stack<int> st;
    bool on_stack[MAX+1]= {0};
    bool visited[MAX+1]= {0};
    for(int i=0; i<nodes; i++) //In case the graph is disconnected
    {
        if(visited[i]) continue; //For time efficiency
        st.push(i);
        while(!st.empty())
        {
            int u=st.top();
            if(!visited[u])
            {
                visited[u]=1;
                on_stack[u]=1;
            }
            else //backtracking, but keeping the visited array unchanged for time efficiency
            {
                on_stack[u]=0;
                st.pop();
                continue;
            }
            for(int j=0; j<adjList[u].size(); j++)
            {
                int v=adjList[u][j];
                if(!visited[v])
                {
                    st.push(v);
                }
                else
                {
                    if(on_stack[v]) return true; //cycle detected
                }
            }
        }
    }
    return false;
}


int main()
{
    vector<vector<int> > adjList(MAX+1);
    int nodes, edges;
    cout<<"Enter the number of nodes: ";
    cin>>nodes;
    cout<<endl;
    cout<<"Enter the number of edges: ";
    cin>>edges;
    cout<<endl;
    cout<<"Enter the pair of edges: "<<endl;
    for(int i=0; i<edges; i++)
    {
        int from, to;
        cin>> from>> to;
        adjList[from].push_back(to);
    }
    if(detectCycle(nodes, adjList)==1) cout<<"Cycle found!"<<endl;
    else cout<<"Cycle not found!"<<endl;
    return 0;
}

SPOJ – PT07Y – Is it a tree

Arunima Mandal 3 Comments

An undirected/directed graph is a tree if anyone know that any two of the following three properties are true:

1. It is connected
2. There are n – 1 edges, where n is the number of nodes
3. There are no cycles

It is better to check if all these three conditions are true, then that graph is surely a tree.
This problem also can be solved with BFS, but I used DFS because of smaller size of code n more simplyness than BFS.
Here, the source is not given so I have assumed the 1st node of the 1st given edge to be the source with the help of a variable x, you can assume any of the node.

#include <bits/stdc++.h>

#define pf                  printf
#define sf(a)               scanf("%d",&a)
#define sfl(a)              scanf("%lld",&a)
#define sff(a,b)            scanf("%d %d",&a,&b)
#define sffl(a,b)           scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)         scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)        scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d)      scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d)     scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e)   scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e)  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a)              scanf("%c",&a)
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define pbp(a,b)            push_back({a,b})
#define db                  double
#define ft                  float
#define ll                  long long
#define ull                 unsigned long long
#define ff                  first
#define ss                  second
#define sz(x)               x.size()
#define qu                  queue
#define pqu                 priority_queue
#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 max3(a, b, c)       max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c)       min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n)          for(int i=0;i<n;i++)
#define loopn(i,n)          for(int i=1;i<n;i++)
#define loop1(i,n)          for(int i=1;i<=n;i++)
#define loopi(i,n)          for(int i=0;i<n-1;i++)
#define loopab(i,a,b)       for(int i=a;i<=b;i++)
#define loopba(i,b,a)       for(int i=b;i>=a;i--)
#define REV(i,n)            for(i=n; i>=0; i--)
#define stlloop(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 case1(z)            cout<<"Case "<<z<<": "
#define case2(z)            printf("Case %d: ",z)
#define PI                  3.14159265358979323846264338328
#define valid(tx,ty)        tx>=0 && tx<row && ty>=0 && ty<col
#define intlim              2147483648
#define MAX                 1000000
#define inf                 100000000

/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/

using namespace std;

vector<int>g[MAX+1];
bool visited[MAX+1];
int c,d;

void dfs(int u)
{
    visited[u]=1;
    for(int i=0; i<g[u].size(); i++)
    {
        int v=g[u][i];
        if(visited[v]) //Checking cycle/loop
        {
            d=1;
            break;
        }
        else
        {
            c++; // Checking connected
            dfs(v);
        }
    }
}
int main()
{
    CIN;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int node,edge;
    cin>>node>>edge;
    int x=0,src;
    for(int i=0; i<edge; i++)
    {
        int from,to;
        cin>>from>>to;
        if(x==0) src=from;
        x=1;
        g[from].push_back(to);
    }

    c=1; // Either the graph is connected or not(Either each vertex is visited once or not)
    d=0; // For checking cycle/loop
    visited[src]=1;
    dfs(src);

    if(!d && c==node && edge==node-1) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

UVa – 429 – Word Transformation

Arunima Mandal Leave a comment

In this problem, since there is no mention of limit of input in a particular test case, so we have assumed the empty string to be the termination. That’s why we have used getline() for taking input instead of cin. Otherwise there is no way of returning to another test case taking only string by cin.

#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 sz(x)           x.size()
#define qu              queue
#define pqu             priority_queue
#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 stlloop(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 case(z,x)       cout<<"Case "<<i<<": "<<x<<endl
#define case(z)         cout<<"Case "<<z<<": "
#define PI              3.14159265358979323846264338328
#define valid(tx,ty)    tx>=0 && tx<r && ty>=0 && ty<c
#define MAX             2000

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

using namespace std;

map<string,vector<string>> mp;

bool check(string a, string b)
{
    int cnt=0;
    if(sz(a)!=sz(b)) return 0;
    else
    {
        loop0(i,sz(a))
        {
            if(a[i]!=b[i]) cnt++;
            if(cnt>1) return 0;
        }
    }
    return cnt==1;
}

int bfs(string src, string dst)
{
    map<string,int>dis;
    map<string,bool>visited;
    queue<string>Q;
    Q.push(src);
    dis[src]=0;
    visited[src]=1;
    while(!Q.empty())
    {
        string u=Q.front();
        Q.pop();
        if(u==dst) return dis[u];
        loop0(i,sz(mp[u]))
        {
            string v=mp[u][i];
            if(!visited[v])
            {
                dis[v]=dis[u]+1;
                visited[v]=1;
                Q.push(v);
            }
        }
    }
}

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

    int t;
    cin>>t;

    for(int z=1; z<=t; z++)
    {
        string str;
        vector<string>v;
        while(cin>>str  && str!="*") v.pb(str);
        loop0(i,sz(v))
        {
            for(int j=i+1; j<sz(v); j++)
                if(check(v[i],v[j]))
                {
                    mp[v[i]].pb(v[j]);
                    mp[v[j]].pb(v[i]);
                }
        }
        getchar();
        string s1;
        while(1)
        {
            getline(cin,s1);
            if(s1=="") break;
            bool x=0;
            string s3,s4;
            loop0(i,sz(s1))
            {
                if(s1[i]==' ')
                {
                    x=1;
                    continue;
                }
                if(!x)
                    s3+=s1[i];
                else
                    s4+=s1[i];
            }
            cout<<s3<<" "<<s4<<" "<<bfs(s3,s4)<<endl;
        }
        if(z!=t) cout<<endl;
        mp.clear();
    }
    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;
}