How to check if an array of strings can form a circle or not?

Implementation of the approach(C++)

#include <bits/stdc++.h>
#define chars 26
using namespace std;
//Class for the graph.
class graph
{
    int nofv;
    //Adjacency list to store the graph.
    list<int> *adjacencylist;
    int *in;
    public:
    //Constructor.
    graph(int nofv);
    //Destructor.
    ~graph()
    {
        delete [] adjacencylist;
        delete [] in;
    }
    //To add an edge to the graph.
    void addingedge(int edgestart, int edgeend)
    {
        adjacencylist[edgestart].push_back(edgeend);
        (in[edgeend])++;
    }
    //To check if a graph is eulerian or not.
    bool checkforeuleriancycle();
    //To check is a graph is strongly connected or not.
    bool checkforstronglyconnected();
    //Function for DFS of a graph.
    void fordfs(int startedge, bool marked[]);
    graph gettranspose();
};
//To create a graph.
graph::graph(int nofv)
{
    this->nofv=nofv;
    adjacencylist = new list<int>[nofv];
    in = new int[nofv];
    for(int i=0;i<nofv;i++)
    {
        in[i]=0;
    }
}
bool graph::checkforeuleriancycle()
{
    //If all non-zero degree vertices are connected.
    if(checkforstronglyconnected()==false)
    {
        return false;
    }
    //Checking if in degree and out degree is same or not.
    for(int i=0;i<nofv;i++)
    {
        if(adjacencylist[i].size()!=in[i])
        {
            return false;
        }
    }
    return true;
}
void graph::fordfs(int startedge, bool marked[])
{
    //To keep track of visited nodes.
    marked[startedge]=true;
    list<int>:: iterator itr;
    //Recursive call for adjacent vertices.
    for( itr=adjacencylist[startedge].begin();itr!=adjacencylist[startedge].end();++itr)
    {
        if(!marked[*itr])
        {
            fordfs(*itr, marked);
        }
    }
}
graph graph::gettranspose()
{
    graph G(nofv);
    for(int startedge=0;startedge<nofv;startedge++)
    {
        list<int>::iterator itr;         for(itr=adjacencylist[startedge].begin();itr!=adjacencylist[startedge].end();++itr)
        {
            //Creating the transpose of the graph.
            G.adjacencylist[*itr].push_back(startedge);
            (G.in[startedge])++;
        }
    }
    return G;
}
//To check if all non-zero degree vertices are strongly connected //or not.
bool graph::checkforstronglyconnected()
{
    //Create an array to keep track of visited nodes.
    bool marked[nofv];
    for(int i=0;i<nofv;i++)
    {
        marked[i]=false;
    }
    //Get first non-zero degree vertex.
    int n;
    for(n=0;n<nofv;n++)
    {
        if(adjacencylist[n].size()>0)
        {
            break;
        }
    }
    //Start DFS with that vertex.
    fordfs(n, marked);
    for(int i=0;i<nofv;i++)
    {
        //If DFS doesn't visit all the vertices, return false.
        if(adjacencylist[i].size()>0 && marked[i]==false)
        {
            return false;
        }
    }
    //Create transpose of the graph.
    graph Gr=gettranspose();
    for(int i=0;i<nofv;i++)
    {
        marked[i]=false;
    }
    //DFS of the transpose of the graph.
    Gr.fordfs(n, marked);
    //If it does not visit all the vertices, return false.
    for(int i=0;i<nofv;i++)
    {
        if(adjacencylist[i].size()>0 && marked[i]==false)
        {
            return false;
        }
    }
    return true;
}
//To check if the array of strings can form a circle or not.
bool circleformed(string str[], int n)
{
    //Create a graph with every character of alphabet as its
    //vertex.
    graph g(chars);
    //For every string create an edge from first to last
    //character of the string.
    for(int i=0;i<n;i++)
    {
        string s = str[i];
        g.addingedge(s[0]-'a', s[s.length()-1]-'a');
    }
    //Check if the graph formed is eulerian or not.
    //If it is eulerian, then it can form a circle, otherwise no.
    return g.checkforeuleriancycle();
}
int main()
{
    //Take no. of strings, and strings as user input.
    int n;
    cout<<"Enter the number of strings in the array, then elements ";
    cin>>n;
    string arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    //Function call to check if it can form the circle or not.
    int X=circleformed(arr, n);
    //Printing the result.
    if(X==1)
    {
        cout<<"The array of strings can form a circle. ";
    }
    else
    {
        cout<<"The array of strings can not form a circle. ";
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input-

4
alsdf fkdjdhl lyywef fwera

Output-

Enter the number of strings in the array, then elements 
The array of strings can form a circle.

Complexity Analysis

Time Complexity: For each of 26 vertexes we traverse n edges (n=number of strings), so the overall complexity is O(n)

Space Complexity:O(n).

Frequently Asked Questions

1. What is a circuit in a graph?
   A circuit is a path in a graph that starts and ends on the same vertex. 
    
2. What is an eulerian circuit in a graph?
   A path in a graph contains each edge exactly once and has the same vertex as the start and endpoint.
    
3. How is a path different from a circuit in the graph?
   A path in a graph is any route formed by the edges, whereas a circuit is a path that starts and ends from the same vertex.
    
4. What do you mean by the adjacency matrix of a graph?
   It is a way of representing a finite graph. In it, we create a matrix by indexing rows and columns with the identical ordering of vertices. Then put one if there is an edge between the vertices at the row and column, else 0.
    
5. What is a cycle in a graph?
   A cycle in a graph is a non-empty trail in a graph, with only identical first and last vertex. 

Key takeaways

In this blog, we learned the solution to the problem in which we are given an array of strings and asked to check if they can form a circle-

We started with creating a graph With 26 characters of the alphabet as its vertices. Then we go through the array of Strings, and for every string, we draw an edge between its first and last characters. Now we check if this graph is an eulerian graph or not with the following conditions-

The indegree and outdegree for each vertex are the same.

All vertices with a non-zero degree must belong to a single strongly connected component.

If both the conditions are true, the graph is an eulerian graph. Else, it is not an eulerian graph.

Now, if the graph is an eulerian graph, the array of strings can form a circle, else they can not form a circle.

Recommended problems -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String

You can read more about strings here and practice similar problems on code studio as well.