CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Oct 2012

    Question 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. #2
    Join Date
    Jul 2005

    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

Windows Mobile Development Center

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)

We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.