Given a array arr[] of n integers. For every value arr[i], we can move to arr[i] + 1 clockwise
considering array elements in cycle. We need to count cyclic elements in the array. An element is cyclic if starting from it and moving to arr[i] + 1 leads to same element.
Examples:
Input : arr[] = {1, 1, 1, 1} Output : 4 All 4 elements are cyclic elements. 1 -> 3 -> 1 2 -> 4 -> 2 3 -> 1 -> 3 4 -> 2 -> 4 Input : arr[] = {3, 0, 0, 0} Output : 1 There is one cyclic point 1, 1 -> 1 The path covered starting from 2 is 2 -> 3 -> 4 -> 1 -> 1. The path covered starting from 3 is 2 -> 3 -> 4 -> 1 -> 1. The path covered starting from 4 is 4 -> 1 -> 1
One simple solution is to check all elements one by one. We follow simple path starting from every element arr[i], we go to arr[i] + 1. If we come back to a visited element other than arr[i], we do not count arr[i]. Time complexity of this solution is O(n2)
An efficient solution is based on below steps.
1) Create a directed graph using array indexes as nodes. We add an edge from i to node (arr[i] + 1)%n.
2) Once a graph is created we find all strongly connected components using Kosaraju’s Algorithm
3) We finally return sum of counts of nodes in individual strongly connected component.
// CPP program to count cyclic points // in an array using Kosaraju's Algorithm #include <bits/stdc++.h> using namespace std; // Most of the code is taken from below link class Graph { int V; list< int >* adj; void fillOrder( int v, bool visited[], stack< int >& Stack); int DFSUtil( int v, bool visited[]); public : Graph( int V); void addEdge( int v, int w); int countSCCNodes(); Graph getTranspose(); }; Graph::Graph( int V) { this ->V = V; adj = new list< int >[V]; } // Counts number of nodes reachable // from v int Graph::DFSUtil( int v, bool visited[]) { visited[v] = true ; int ans = 1; list< int >::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) ans += DFSUtil(*i, visited); return ans; } Graph Graph::getTranspose() { Graph g(V); for ( int v = 0; v < V; v++) { list< int >::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) g.adj[*i].push_back(v); } return g; } void Graph::addEdge( int v, int w) { adj[v].push_back(w); } void Graph::fillOrder( int v, bool visited[], stack< int >& Stack) { visited[v] = true ; list< int >::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) fillOrder(*i, visited, Stack); Stack.push(v); } // This function mainly returns total count of // nodes in individual SCCs using Kosaraju's // algorithm. int Graph::countSCCNodes() { int res = 0; stack< int > Stack; bool * visited = new bool [V]; for ( int i = 0; i < V; i++) visited[i] = false ; for ( int i = 0; i < V; i++) if (visited[i] == false ) fillOrder(i, visited, Stack); Graph gr = getTranspose(); for ( int i = 0; i < V; i++) visited[i] = false ; while (Stack.empty() == false ) { int v = Stack.top(); Stack.pop(); if (visited[v] == false ) { int ans = gr.DFSUtil(v, visited); if (ans > 1) res += ans; } } return res; } // Returns count of cyclic elements in arr[] int countCyclic( int arr[], int n) { int res = 0; // Create a graph of array elements Graph g(n + 1); for ( int i = 1; i <= n; i++) { int x = arr[i-1]; // If i + arr[i-1] jumps beyond last // element, we take mod considering // cyclic array int v = (x + i) % n + 1; // If there is a self loop, we // increment count of cyclic points. if (i == v) res++; g.addEdge(i, v); } // Add nodes of strongly connected components // of size more than 1. res += g.countSCCNodes(); return res; } // Driver code int main() { int arr[] = {1, 1, 1, 1}; int n = sizeof (arr)/ sizeof (arr[0]); cout << countCyclic(arr, n); return 0; } |
Output:
4
Time Complexity : O(n)
Auxiliary space : O(n) Note that there are only O(n) edges.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments