CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Effective way to solve this problem

1. Junior Member
Join Date
Oct 2012
Posts
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.

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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•