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