limboguard's blog

By limboguard, history, 5 months ago, In English,


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++;
	for(int child : g[u])
			dfs(child , step+1, s);
        visited[u] = false;

could somebody help me finding complexity?

  • Vote: I like it
  • 0
  • Vote: I do not like it

5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

It's a standard recursion which works in $$$O(size~of~answer) = O(N^{K-1})$$$