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)$.
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 $n1$ 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. 


The answer for directed acyclic graphs is no: in any standard adjacencylist based representation you have to look at $\Omega(m)$ of the edges; it is not enough to look at $O(n)$ vertices and edges, even if the vertices are already labeled by indegree and outdegree and the adjacency lists are partitioned into incoming and outgoing edges. For, suppose that you have a directed acyclic graph in the form of a directed path (with $n1$ edges), partitioned into four equal length subpaths $a_1\dots a_{n/4}$, $b_1\dots b_{n/4}$, $c_1\dots c_{n/4}$, and $d_1\dots d_{n/4}$. For some number of pairs $(i,j)$, add to this path the additional edges in the threeedge path $a_ib_jc_id_j$. This allows the addition of numbers of additional edges ranging from none to $\Omega(n^2)$, and the graph formed in this way is acyclic. But, if your algorithm fails to examine at least one of the edges in any one of these threeedge paths, it could instead be replaced by a path $a_ic_ib_jd_j$, producing a graph with the same indegrees and outdegrees that is not acyclic and that your algorithm cannot distinguish from the given acyclic graph. This construction doesn't work directly for adjacency matrix representations but in that representation, too, you need more than a linear number of queries; see the Aanderaa–Karp–Rosenberg conjecture and note that the property of containing a cycle is monotone. 


Well, I think I this thing works : Take any vertex, and start a dephtfirst.
The point is : if you take a vertex u such that there is a directed path from one of its outneighbors n1 to one of its inneighbors n2, then a depthfirstsearch starting from n1 WILL discover n2 (which will in turn rediscover u  you found your circuit). By the way, this algorithm is not in $O(n)$ but in $O(m)$. I posted it because I really don't know how to be more efficient (let's face it, any implemented version of DFS is  FAST).... I'd be glad to know a better one though :) Nathann 

