Check if a set of words can be rearranged to form a circle
Given a set of words, check if the individual words can be rearranged to form a circle. Two words, X and Y, can be put together in a circle if the last character of X is the same as the first character of Y or vice-versa.
For example,
Consider the following set of words:
[ANT, OSTRICH, DEER, TURKEY, KANGAROO, TIGER, RABBIT, RAT, TOAD, YAK, HYENA]
The words can be rearranged as follows to form a circle. Note that, for any pair of consecutive words (X → Y) in the circle, the last character of the word X is the same as the first character of the word Y.
ANT → TIGER → RABBIT → TOAD
↑ ↓
HYENA DEER
↑ ↓
OSTRICH RAT
↑ ↓
KANGAROO ← YAK ← TURKEY
[ANT, OSTRICH, DEER, TURKEY, KANGAROO, TIGER, RABBIT, RAT, TOAD, YAK, HYENA]
The words can be rearranged as follows to form a circle. Note that, for any pair of consecutive words (X → Y) in the circle, the last character of the word X is the same as the first character of the word Y.
ANT → TIGER → RABBIT → TOAD
↑ ↓
HYENA DEER
↑ ↓
OSTRICH RAT
↑ ↓
KANGAROO ← YAK ← TURKEY
Prerequisite:
The idea is to build a directed graph and for each word in the given set, add an edge from the first character to the last character in the graph. Now the problem is reduced to finding an Eulerian cycle in the constructed graph. If the graph has an eulerian circuit, then a circle can be formed; otherwise, not. A directed graph has an Eulerian cycle if and only if:
- Every vertex has
in-degree == out-degree, and - All of its non-isolated vertices belong to a single strongly connected component.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Define the alphabet size for graph vertices #define CHAR_SIZE 128 // A class to represent a graph object class Graph { public: // A vector of vectors to represent an adjacency list vector<vector<int>> adjList; // Constructor Graph(int n) { // resize the vector to hold `n` elements adjList.resize(n); } // Utility function to add an edge (u, v) to the graph void addEdge(int u, int v) { adjList[u].push_back(v); } }; // Utility function to perform DFS traversal on the graph void DFS(Graph const &graph, int u, vector<bool> &visited) { // mark the current node as visited visited[u] = true; // do for every edge (u, v) for (int v: graph.adjList[u]) { // recur if `v` is not visited if (!visited[v]) { DFS(graph, v, visited); } } } // Function to create transpose of a graph Graph transpose(Graph const &graph, int n) { Graph g(n); // for every edge (u, v), create a reverse edge (v, u) for (int u = 0; u < n; u++) { for (int v: graph.adjList[u]) { g.addEdge(v, u); } } return g; } // Function to check if all non-isolated vertices in a graph are visited bool isVisited(Graph const &graph, const vector<bool> &visited) { for (int i = 0; i < visited.size(); i++) { if (graph.adjList[i].size() && !visited[i]) { return false; } } return true; } // Function to check if all non-isolated vertices in a graph belong to a // single strongly connected component bool isSC(Graph const &graph, int n) { // keep track of all previously visited vertices vector<bool> visited(n); // start DFS from the first vertex `i` with a non-zero degree int i; for (i = 0; i < n; i++) { if (graph.adjList[i].size()) { DFS(graph, i, visited); break; } } // return false if DFS could not explore all non-isolated vertices if (!isVisited(graph, visited)) { return false; } // reset the visited vertices array for another DFS call fill(visited.begin(), visited.end(), false); // create a transpose graph with the direction of every edge reversed Graph g = transpose(graph, n); // perform DFS on the transpose graph using the same starting vertex `i` DFS(g, i, visited); // check if the second DFS also explored all non-isolated vertices return isVisited(g, visited); } // Function to check if a given set of words can be rearranged to form a circle bool checkArrangement(vector<string> const &words) { // create a directed graph with the same number of nodes as the alphabet size Graph graph(CHAR_SIZE); // create an empty array to store in-degree for each vertex // assign in-degree 0 to each vertex vector<int> in(CHAR_SIZE); // process each word for (const string &s: words) { int src = s.front(); int dest = s.back(); // add an edge to the graph from the first character to the last character graph.addEdge(src, dest); // increment the in-degree of the destination vertex by 1 in[dest]++; } /* If the constructed graph has an Eulerian cycle, only then can the given words be rearranged to form a circle */ // 1. Check if every vertex has the same in-degree and out-degree for (int i = 0; i < CHAR_SIZE; i++) { if (graph.adjList[i].size() != in[i]) { return false; } } // 2. Check if all non-isolated vertices belong to a single // strongly connected component return isSC(graph, CHAR_SIZE); } int main() { vector<string> words = { "ANT", "OSTRICH", "DEER", "TURKEY", "KANGAROO", "TIGER", "RABBIT", "RAT", "TOAD", "YAK", "HYENA" }; if (checkArrangement(words)) { cout << "The given words can be rearranged"; } else { cout << "The given words cannot be rearranged"; } return 0; } |
Output:
The given words can be rearranged
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 |
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; // A class to represent a graph object class Graph { // A list of lists to represent an adjacency list List<List<Integer>> adjList; // stores indegree of a vertex List<Integer> in; // Constructor Graph(int n) { adjList = new ArrayList<>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); } // initialize indegree of each vertex by 0 in = new ArrayList<>(Collections.nCopies(n, 0)); } // Utility function to add an edge (u, v) to the graph void addEdge(int u, int v) { // add an edge from source to destination adjList.get(u).add(v); // increment in-degree of destination vertex by 1 in.set(v, in.get(v) + 1); } } class Main { public static final int CHAR_SIZE = 128; // Utility function to perform DFS traversal on the graph public static void DFS(Graph graph, int v, boolean[] discovered) { // mark the current node as discovered discovered[v] = true; // do for every edge (v, u) for (int u: graph.adjList.get(v)) { // `u` is not discovered if (!discovered[u]) { DFS(graph, u, discovered); } } } // Function to create transpose of a graph public static Graph transpose(Graph graph, int n) { Graph g = new Graph(n); // for every edge (u, v), create a reverse edge (v, u) for (int u = 0; u < n; u++) { for (int v: graph.adjList.get(u)) { g.addEdge(v, u); } } return g; } // Function to check if all non-isolated vertices in a graph are visited public static boolean isVisited(Graph graph, boolean[] visited) { for (int i = 0; i < visited.length; i++) { if (graph.adjList.get(i).size() > 0 && !visited[i]) { return false; } } return true; } // Function to check if all non-isolated vertices in a graph belong to a // single strongly connected component public static boolean isSC(Graph graph, int n) { // keep track of all previously visited vertices boolean[] visited = new boolean[n]; // start DFS from the first vertex `i` with a non-zero degree int i; for (i = 0; i < n; i++) { if (graph.adjList.get(i).size() > 0) { DFS(graph, i, visited); break; } } // return false if DFS could not explore all non-isolated vertices if (!isVisited(graph, visited)) { return false; } // reset the visited vertices array for another DFS call Arrays.fill(visited, false); // create a transpose graph with the direction of every edge reversed Graph g = transpose(graph, n); // perform DFS on the transpose graph using the same starting vertex `i` DFS(g, i, visited); // check if the second DFS also explored all non-isolated vertices return isVisited(g, visited); } // Function to check if a given set of words can be rearranged to form a circle public static boolean checkArrangement(String[] words) { // create a directed graph with the same number of nodes as the alphabet size Graph graph = new Graph(CHAR_SIZE); // create an empty array to store in-degree for each vertex // assign in-degree 0 to each vertex int[] in = new int[CHAR_SIZE]; // process each word for (String s: words) { int src = s.charAt(0); int dest = s.charAt(s.length() - 1); // add an edge to the graph from the first character to the last character graph.addEdge(src, dest); // increment the in-degree of the destination vertex by 1 in[dest]++; } /* If the constructed graph has an Eulerian cycle, only then can the given words be rearranged to form a circle */ // 1. Check if every vertex has the same in-degree and out-degree for (int i = 0; i < CHAR_SIZE; i++) { if (graph.adjList.get(i).size() != in[i]) { return false; } } // 2. Check if all non-isolated vertices belong to a single // strongly connected component return isSC(graph, CHAR_SIZE); } public static void main(String[] args) { String[] words = { "ANT", "OSTRICH", "DEER", "TURKEY", "KANGAROO", "TIGER", "RABBIT", "RAT", "TOAD", "YAK", "HYENA" }; if (checkArrangement(words)) { System.out.println("The given words can be rearranged"); } else { System.out.println("The given words cannot be rearranged"); } } } |
Output:
The given words can be rearranged
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
# define alphabet size for graph vertices CHAR_SIZE = 128 # A class to represent a graph object class Graph: def __init__(self, n, edges=[]): # resize the list to hold `n` elements self.adjList = [[] for _ in range(n)] # add an edge from source to destination for (src, dest) in edges: self.addEdge(src, dest) # Function to add an edge (u, v) to the graph # and update in-degree for each edge def addEdge(self, u, v): self.adjList[u].append(v) # Function to perform DFS traversal on the graph def DFS(graph, v, discovered): discovered[v] = True # mark the current node as discovered # do for every edge (v, u) for u in graph.adjList[v]: if not discovered[u]: # `u` is not discovered DFS(graph, u, discovered) # Function to create transpose of a graph def transpose(graph, n): g = Graph(n) # for every edge (u, v), create a reverse edge (v, u) for u in range(n): for v in graph.adjList[u]: g.addEdge(v, u) return g # Function to check if all non-isolated vertices in a graph are discovered def isdiscovered(graph, discovered): for i in range(len(discovered)): if len(graph.adjList[i]) and not discovered[i]: return False return True # Function to check if all non-isolated vertices in a graph belong to a # single strongly connected component def isSC(graph, n): # keep track of all previously discovered vertices discovered = [False] * n # start DFS from the first vertex `i` with a non-zero degree for i in range(n): if len(graph.adjList[i]): DFS(graph, i, discovered) break # return false if DFS could not explore all non-isolated vertices if not isdiscovered(graph, discovered): return False # reset the discovered vertices array for another DFS call discovered[:] = [False] * n # create a transpose graph with the direction of every edge reversed g = transpose(graph, n) # perform DFS on the transpose graph using the same starting vertex `i` DFS(g, i, discovered) # check if the second DFS also explored all non-isolated vertices return isdiscovered(g, discovered) # Function to check if a given set of words can be rearranged to form a circle def checkArrangement(words): # create a directed graph with the same number of nodes as the alphabet size graph = Graph(CHAR_SIZE) # create an empty array to store in-degree for each vertex # assign in-degree 0 to each vertex indegree = [0] * CHAR_SIZE # process each word for s in words: src = ord(s[0]) dest = ord(s[-1]) # add an edge to the graph from the first character to the last character graph.addEdge(src, dest) # increment the in-degree of the destination vertex by 1 indegree[dest] += 1 ''' If the constructed graph has an Eulerian cycle, only then can the given words be rearranged to form a circle ''' # 1. Check if every vertex has the same in-degree and out-degree for i in range(CHAR_SIZE): if len(graph.adjList[i]) != indegree[i]: return False # 2. Check if all non-isolated vertices belong to a single # strongly connected component return isSC(graph, CHAR_SIZE) if __name__ == '__main__': words = [ 'ANT', 'OSTRICH', 'DEER', 'TURKEY', 'KANGAROO', 'TIGER', 'RABBIT', 'RAT', 'TOAD', 'YAK', 'HYENA' ] if checkArrangement(words): print('The given words can be rearranged') else: print('The given words cannot be rearranged') |
Output:
The given words can be rearranged
The time complexity of the above solution is the same as that of Kosaraju’s algorithm, i.e., O(V + E), where V and E are the total number of vertices and edges in the graph, respectively.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)