# Effective way to solve this problem

• October 12th, 2012, 10:34 AM
Serillan
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 :D)
Sry for some english mistakes.
• October 12th, 2012, 10:45 AM
D_Drmmr
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.