-
October 12th, 2012, 10: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, 10: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
|