CODEWITHSUNDEEP
c++algorithm
Serillan
Serillan

Reputation: 193

Effective algorithm for this program

I have to do the program which takes from user:
n - number of elements
m - the number of pairs (two elements are in pair)
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 others elements of that number.
for example:

INPUT: (first row n and m) next rows there are pairs

                                 5 6           
                                 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 the 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

Upvotes: 2

Views: 222

Answers (1)

Abe Schneider
Abe Schneider

Reputation: 987

If I understand your problem correctly, you could keep an array of 10 elements (0-9), and then for each element keep another array of booleans of whether a pair was observed:

bool pairs[10][10];

When you see the pair (1,2), you could do:

pairs[1][2] = true;

To figure out which number has the most pairs, you can just sum up the boolean values.

However, you do have a problem that you want (1, 2) to be the same as (2, 1). To deal with that, you could impose an order:

void order(int &a, int &b) {
    if (b < a) swap(a, b);
}

Upvotes: 1

Related Questions