I wonder if I can make an algorithm to check if a given graph $G=(V,E)$ is acyclic or not with the complexity of $O(|V|)$.
I modified the BFS algorithm to do this, but the complexity seems to be $O(|V|+|E|)$.



Is it possible to check a graph for acyclicity in $O(|V|)$ time?
If a graph on $n$ nodes has $n$ or more edges then it has a cycle (since trees are the acyclic graphs with the greatest number of edges and have exactly $n-1$ edges). So if your BFS ever traverses $n$ or more edges you may immediately stop and report that the graph has a cycle. Otherwise BFS terminates in $O(n)$ time as there are $n$ nodes and fewer than $n$ edges. In either case the runtime is $O(n)$.


EDIT: As Gerhard Paseman's comment points out this answer assumes an undirected graph.


