Archive for category Acm

Longest path!


The problem taken form acm uva site , Longest Path

Since we need to know the longest path for a source node given, the graph of cities to be traversed in DFS. The Depth First Traversal visits all nodes reachable from the source node. Here is the function needed for DFS in this problem.

void dfs(long snode)
{
long i;
if(sum>max)
{
max=sum;
p=snode;
}
for(i=0;i<num;i++)
{
if(n[snode][i]==1&&visited[snode][i]==0&&i!=start)
{
visited[snode][i]=1;
sum++;
dfs(i);
sum--;
visited[snode][i]=0;
}
}
}

dfs.png

Advertisements

1 Comment