Click here to Skip to main content
15,890,185 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
My approach : using recursive DFS.

Note: i will be running this function for every vertex of graph and this approach works for very small values of vertices. How can i improve it or could u suggest any better/faster algo. Thanks:)


What I have tried:

static int size=0,source=0;

int ans=0;

void moddfs(int** edges,int N,int s,int visited[])

{

visited[s]=1;

if(size<3)

{

for(int i=0;i<N;i++)

{

if(size==0)

{

source=s;

}

if(!visited[i] && edges[s][i])

{

size++;

moddfs(edges,N,i,visited);

}

}

}

else{

if(edges[source][s])

{

ans++;

}

}

visited[s]=0; size--;

}
Posted
Updated 4-Aug-19 6:28am

1 solution

Quote:
How can i improve it or could u suggest any better/faster algo.

Show the calling code with sample data so we have an idea of what you do with this function.

Advise:
- Double line spacing adds nothing to your code, it just make it more difficult to read.
- Learn to indent properly your code, it show its structure and it helps reading and understanding. It also helps spotting structures mistakes.
C++
static int size=0,source=0;
int ans=0;
void moddfs(int** edges,int N,int s,int visited[])
{
    visited[s]=1;
    if(size<3)
    {
        for(int i=0;i<N;i++)
        {
            if(size==0)
            {
                source=s;
            }
            if(!visited[i] && edges[s][i])
            {
                size++;
                moddfs(edges,N,i,visited);
            }
        }
    }
    else{
        if(edges[source][s])
        {
            ans++;
        }
    }
    visited[s]=0;
    size--;
}

Indentation style - Wikipedia[^]

Professional programmer's editors have this feature and others ones such as parenthesis matching and syntax highlighting.
Notepad++ Home[^]
ultraedit[^]

[Update]
Quote:
How can i improve it or could u suggest any better/faster algo.

Sure I can give you directly a solution, but it will be magic to you, you will learn nothing from it.
Improving an algorithm is optimization.
There is basically 2 aspects:
- Code optimization: when code is inefficient because of quick and dirty writing. You can use profiling to spot bottle necks. Profiling (computer programming) - Wikipedia[^]
- Algorithm optimization: This is where you can gain big. This means a deep understanding of the problem and of algorithm used. The cycles 1234, 2341, 3412, 4123, 4321, 3214, 2143 and 1432 are all the same cycle, you have to establish rules to keep only 1 of them.
You have to see if other rules can do the trick and be more efficient.
Example: say that first node in cycle is the minimum node number in the cycle, it lead to an improvement because you don't need to try possible links with lower nodes number trough the cycle.
Is recursion the best way to get answers ?
...
 
Share this answer
 
v3
Comments
StoneCoder 4-Aug-19 21:05pm    
Thanku for commenting. I will definitely keep ur advice in mind. Here is my driver code:

int main()
{
int N;
cin>>N;
int **edges;
edges=(int**)malloc(sizeof(int*)*N);
for(int i=0;i<n;i++)
{
="" edges[i]="(int*)malloc(sizeof(int)*N);
" for(int="" j="0;j<N;j++)
" cin="">>edges[i][j];
}
}
int visited[N];
for(int i=0;i
Patrice T 4-Aug-19 22:28pm    
Use Improve question to update your question.
So that everyone can pay attention to this information.
End of code is missing.
StoneCoder 4-Aug-19 21:08pm    
input:
8
0 1 0 1 1 0 0 0
1 0 1 0 0 1 0 0
0 1 0 1 0 0 1 0
1 0 1 0 0 0 0 1
1 0 0 0 0 1 0 1
0 1 0 0 1 0 1 0
0 0 1 0 0 1 0 1
0 0 0 1 1 0 1 0
Output: 6
StoneCoder 6-Aug-19 11:06am    
That's a thinker!! I will think on the points u mentioned. :)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900