To detect a cycle in a directed graph using depth-first search (DFS), you can keep track of the nodes you have visited during the search. If you encounter a node that you have visited before, it indicates the presence of a cycle.

  Here is a step-by-step algorithm to detect a cycle using DFS:

  1. Initialize a visited array to keep track of visited nodes.

  2. Perform a DFS starting from each unvisited node in the graph.

  3. For each node v, mark it as visited and recursively visit all its adjacent nodes.

  4. While visiting each adjacent node u of v, check if u is already visited. If it is, then there is a cycle in the graph.

  5. If DFS completes without encountering any cycles, repeat the process for the remaining unvisited nodes in the graph.

  6. If all nodes are visited without detecting a cycle, then the graph is acyclic.

  7. Once all nodes are visited or a cycle is found, the algorithm terminates.

  The time complexity of this algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph. It visits each vertex once and each edge once during the DFS traversal.

  It is worth mentioning that this algorithm assumes that the graph is represented as an adjacency list or adjacency matrix. If the graph is given as an adjacency matrix, the time complexity would be O(V^2), since checking each adjacent node would take O(V) time.

  Furthermore, this algorithm only works for directed graphs. If you need to detect cycles in undirected graphs, you would need to use a different approach, such as the Union-Find algorithm or the Tarjan's algorithm.