539 - The Settlers of Catan

[brianfry713]

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

[Mukit Chowdhury]

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

[mntamim]

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]

That is AC code.

[vsha041]

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]

The number of nodes n (2 <= n <= 25) and the number of edges m (1 <= m <= 25). Nodes have degrees of three or less.

[vsha041]

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]

I'm not understanding what you're asking.
http://en.wikipedia.org/wiki/Longest_path_problem