### limboguard's blog

By limboguard, history, 4 weeks ago, ,

Hi!

So I made an algorithm to find the number of cycles of length K in a graph by using a DFS that finds all paths with k-1 vertices that include the starting vertex. But I am not sure about the complexity since it seems to be higher than the normal O(V+E). The parameters are current vertex, length of the path (initially = 1) and starting vertex. The DFS code (Java but understandable with c++):

private static void dfs (int u, int step, int s) {
visited[u] = true;

if(step == k){
visited[u] = false;
if(g[u].contains(s)) ans++;
return;
}

for(int child : g[u])
if(!visited[child])
dfs(child , step+1, s);

visited[u] = false;
}


could somebody help me finding complexity?

• 0

 » 4 weeks ago, # |   +3 It's a standard recursion which works in $O(size~of~answer) = O(N^{K-1})$