
October 12th, 2012, 11:34 AM
#1
Effective way to solve this problem
I have to do the program which takes from user:
n  number of elements
m  how many pairs the elements have
then user will write all pairs > 1 and 2; 1 and 3, ...
And output should the number which have the most elements >> where every element is in pair with all elements of that number.
for example: INPUT: 5 6 // n and m
1 2
1 3
1 4
1 5
3 2
4 2
OUTPUT: 1 2 3 or 4 1 2 (1 2 3 4 is not good because elements 3 and 4 aren't in pair)
(1 5 is also not good because 1 5 are in pair but they aren't the biggest)
I need to get this program working under 2 seconds with n = 100000 and m up to 300000
Is there some effective way to do it? I've tried to do it with all combinations and then I checked if all elements are in pair but it's not effective way (100 years to do it like that )
Sry for some english mistakes.

October 12th, 2012, 11:45 AM
#2
Re: Effective way to solve this problem
Your problem can be represented as a graph, where each pair is an edge. Then the problem is to find the largest connected component. I think you can find some efficient algorithms for that if you search a bit.
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it.  P. D. Ouspensky
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This is a CodeGuru survey question.
Featured
