## 539 - The Settlers of Catan

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 539 why wa ..plz help

I looked at the version you messaged me. There mx is an int but you use printf("%ld\n", mx);

Try this input:

Code: Select all

``````3 2
0 1
0 2
0 0``````
Check input and AC output for thousands of problems on uDebug!

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 539 why wa ..plz help

Thanks brianfry713 !!! I have got it Accepted !!!!

mntamim
New poster
Posts: 8
Joined: Wed Nov 06, 2013 12:08 am

### Re: 539 why wa ..plz help

HELP
what am i not taking into account everything seems correct to me

Code: Select all

``````#include <stdio.h>
#include <iostream>
#include <queue>
#include <map>
#include <string>
#include <list>
#include <vector>
#include <math.h>

using namespace std;

int    nodes;
int    edges;
int** matrix;

int vmax = 0;

void traverse(int a,int depth)
{
if(depth > vmax)
vmax = depth;

for(int i=0 ; i<nodes ; i++)
{
if(matrix[a][i]>0)
{
matrix[a][i]--;
matrix[i][a]--;
traverse(i,depth+1);
matrix[a][i]++;
matrix[i][a]++;
}
}
}

int main()
{
//freopen("input.txt","r",stdin);

int a,b;

for(cin >> nodes >> edges; nodes != 0 ; cin >> nodes >> edges)
{
vmax = 0;
matrix = new int*[nodes];

for(int i=0 ; i<nodes ; i++)
{
matrix[i] = new int[nodes];
for(int j=0 ; j<nodes ; j++)
matrix[i][j] = 0;
}

for(int i=0 ; i<edges ; i++)
{
cin >> a >> b;
matrix[a][b]++;
matrix[b][a]++;
}

for(int i=0 ; i<nodes ; i++)
{
traverse(i,0);
}

for(int i=0 ; i<nodes ; i++)
delete[] matrix[i];
delete[] matrix;

cout << vmax << endl;
}

return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 539 why wa ..plz help

That is AC code.
Check input and AC output for thousands of problems on uDebug!

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

### Re: 539 why wa ..plz help

Can someone explain as to why for this problem running DFS from every node can give us longest path in a graph? It works but I think longest path problem in a graph is NP-Complete. Then how come there is a solution in polynomial time?

Thanks.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 539 why wa ..plz help

The number of nodes n (2 <= n <= 25) and the number of edges m (1 <= m <= 25). Nodes have degrees of three or less.
Check input and AC output for thousands of problems on uDebug!

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

### Re: 539 why wa ..plz help

Thanks Bryan. But are you saying that graph is small? Even if graph is big - say 1 million vertices and 10^12 edges. If we run DFS from every node then the run time will still be O(V^4). But longest path problem is NP Complete. Can you please elaborate a bit? Thanks for your time.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 539 why wa ..plz help

I'm not understanding what you're asking.
http://en.wikipedia.org/wiki/Longest_path_problem
Check input and AC output for thousands of problems on uDebug!