539 - The Settlers of Catan

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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

Post by 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
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

Post by Mukit Chowdhury »

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

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 539 why wa ..plz help

Post by brianfry713 »

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

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 539 why wa ..plz help

Post by 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.
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

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 539 why wa ..plz help

Post by brianfry713 »

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!

Post Reply

Return to “Volume 5 (500-599)”