C++ Program to find if the strings can be chained to form a circle

So, we’ll discuss how an array/vector of strings in C++ can be chained together to form a circle or loop. So to start with it lets first understand the topic.

Chain of Strings

Two or more strings can form a chain if the ending character of the first string is starting character of other string and process followed on all the array elements are connected.

Chain to form a circle

Now while connecting them at the end we have to ensure that the ending character of the last element of the chain is the first character of the initial element of the chain to complete the Circle.

Let’s take an example of a vector of strings:

vector<string> a {"acd", "efg", "dbe", "gta"};

In this example, strings can be chained such that they form a complete cycle (You can rearrange them as required).

See the below illustration to understand it better:

Chain String

As you can see in the above example we have drawn a graph using the first and last character of every string and connected them in order of occurrence.
So we will check each string and draw an edge between two vertices of first and last character.
Now to check if the graph has a loop that visits all the vertex in the graph, we will be checking the following conditions:

  • The graph must be connected (multiple graphs must not be formed).
  • Indegree and Outdegree of each vertex should be equal.

For checking the connectivity we will implement DFS in the graph if all the vertices are visited then we will return true otherwise false.
For checking the In and Out degree we’ll simply maintain a vector for them and check if both values are equal.

We’ll declare a 2d Vector to store edges, this will represent a graph, and maintain another array that will record which character from all the alphabets has to be used and mark them as true and in the last 2 vectors for In and Out Degree of each vertex.

vector<vector<int>> chain(26);

vector<int> inD(26), outD(26); 

vector<bool> visitedVertex(26);

int n = a.size(), first, last;

/*
Looping through the vector of strings and performing the initial
operation of marking the character as visited (true) and
counting the degree of each charcter.
*/
for(int i = 0; i < n; i++){
    first = a[i][0] - 'a';
    last = a[i][a[i].size() - 1] - 'a';

    visitedVertex[first] = visitedVertex[last] = true;

    inD[last]++;
    outD[first]++;

    chain[first].push_back(last);
}

Checking In and Outdegree are equal or not, if not directly returning false.

for(int i = 0; i < 26; i++){
    if(inD[i] != outD[i]){
        return false;
    }
}

Further checking if the complete chain is formed or not.

bool chainFormed(vector<vector<int>> chain, vector<bool> visitedVertex, int x){
    vector<bool> visited(26);
   // DFS funtion to perform DFS and update the visited vector.
    DFS(chain, visited, x);

    for(int i = 0; i < 26; i++){
        // If any of the visitedVertex (marked character)
        // is not visited by DFS then return false
        // that means loop is not present.
        if(visitedVertex[i] && !visited[i]){
            return false;
        }
    }
    return true;
}

Full Implementation C++ code to find if the strings can be chained to form a circle:

//author @Nishant

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

void DFS(vector<vector<int>> chain, vector<bool>& visited, int x);
bool chainFormed(vector<vector<int>> chain, vector<bool> visitedVertex, int x);
bool canBeChained(vector<string> a);

int main(){
    vector<string> a {"acd", "efg", "dbe", "gta"};
    if(canBeChained(a)){
        cout << "The given set of strings can be chained to form a circle" << endl;
    }else{
        cout << "The given set of strings can not be chained to form a circle" << endl;
    }
    return 0;
}

/*
Recursive DFS Approach
*/
//make sure use pass reference of visited otherwise visited won't be updated
void DFS(vector<vector<int>> chain, vector<bool>& visited, int x){
    visited[x] = true;
    for(int i = 0; i < chain[x].size(); i++){
        if(!visited[chain[x][i]]){
            DFS(chain, visited, chain[x][i]);
        }
    }
}

bool chainFormed(vector<vector<int>> chain, vector<bool> visitedVertex, int x){
    vector<bool> visited(26);
    
    DFS(chain, visited, x);

    for(int i = 0; i < 26; i++){
        if(visitedVertex[i] && !visited[i]){
            return false;
        }
    }
    return true;
}

bool canBeChained(vector<string> a){
    //creating a 2d vector to store the edges formed
    vector<vector<int>> chain(26);

    vector<int> inD(26), outD(26); 

    // To store if that character is in graph or not
    vector<bool> visitedVertex(26);

    int n = a.size(), first, last;

    for(int i = 0; i < n; i++){
        first = a[i][0] - 'a';
        last = a[i][a[i].size() - 1] - 'a';

        visitedVertex[first] = visitedVertex[last] = true;

        inD[last]++;
        outD[first]++;

        chain[first].push_back(last);
    }

    for(int i = 0; i < 26; i++){
        if(inD[i] != outD[i]){
            return false;
        }
    }

    return chainFormed(chain, visitedVertex, a[0][0] - 'a');
}

Leave a Reply

Your email address will not be published. Required fields are marked *