Click here to Skip to main content
14,639,623 members
Rate this:
Please Sign up or sign in to vote.
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

Rate this:
Please Sign up or sign in to vote.

Solution 1

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.
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 ?
...
   
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, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100