Head to Tail ordering

Head to Tail ordering

A head to tail ordering of strings is the one in which the last letter of the previous word is the same as the first letter of the following word. For eg. ‘Geekforgeeks’ can be followed by ‘ software’.

The task is to write a code to accept a set of finite strings and determine if such an ordering is possible by arranging them in a head to tail sequence.

"Head to tail ordering is possible." if it is possible to arrange all the words in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once else output "Head to tail ordering is not possible.". Output of all the test cases should be in a seperate line and dont print quotes.

Input:
1
3
big
smart
geeks

Output:
Head to tail ordering is possible.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges).

In topological sorting, we use a temporary stack. We don't print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

Head to tail ordering is possible if and only if the generated graph contains a path or a cycle that uses every edge (i.e. word) exactly once. This by definition means there exists an Eulerian path or an Eulerian cycle in the graph.

A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected component.
A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.

#include <bits/stdc++.h>
using namespace std;

int main() {
    //code
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        int n;
        cin>>n;
        unordered_map<char,int> st,ed;
        for(int i=0;i<n;++i)
        {
        cin>>s;
        st[s[0]]++;
        ed[s[s.size()-1]]++;
        }
        int cnt=0;
        for(auto i=ed.begin();i!=ed.end();++i)
        {
            if(st[i->first]!=0)
            {
                if(i->first>0)
                {
                    i->second-=1;
                    ++cnt;
                }
            }
        }
        if(cnt+1==n||n==1)
        cout<<"Head to tail ordering is possible."<<'\n';
        else
        cout<<"Head to tail ordering is not possible."<<'\n';
    }
    return 0;
}