Input:

Output:

Recall the stable matching problem: you are given two disjoint sets, along with preference lists for each element of each set, ranking all elements of the other set. Design an O(n2) algorithm that determines if there exist two completely different stable matchings for the given data. Two stable matchings, M1 and M2, are considered completely different if they share no common pairings. That is, if pairing (x, y) E M1, then (x, y) M2. Input specification: the first line contains the value n, indicating the number of elements in each group. (In the remainder of the input, the elements of a group are referred to by an integer index in the range [0,n-1].) Following this are 2*n lines of data. The first n lines contain the preference lists for the elements of the first group. The first of these lines contains the preference list for element 0 of the first group. The next line contains the preference list for element 1 of the first group, and so forth. The next n lines contain the preference lists for the elements of the second group. The first of these lines contains the preference list for element 0 of the second group. The next line contains the preference list for element 1 of the second group, and so forth. Each line of data representing a preference list contains n numbers, separated by spaces. Specifically, it contains some permutation of the integers in the range [0,n-1]. The values are ordered from highest preference to lowest preference. You may assume all values fit in a 32-bit integer. Output specification: the output contains a single line, containing either the string "YES", or the string "NO", and ending with the end- of-line character ' '. The output should be "YES" if there two completely different stable matchings exist for this input. The output should be "NO" otherwise. Initialize each person to be free. while (some prof is free and hasn't asked every student) { Choose such a prof p s = 1st student on p's list whom p has not yet asked if (s is free) assign p and s to be partners else if (s prefers p to current partner p'). assign p and s to be partners, and p' to be free else s rejects p 31420 42013 10 4312 21034 14023 13240 02431 142310 30241 20314 YES Recall the stable matching problem: you are given two disjoint sets, along with preference lists for each element of each set, ranking all elements of the other set. Design an O(n2) algorithm that determines if there exist two completely different stable matchings for the given data. Two stable matchings, M1 and M2, are considered completely different if they share no common pairings. That is, if pairing (x, y) E M1, then (x, y) M2. Input specification: the first line contains the value n, indicating the number of elements in each group. (In the remainder of the input, the elements of a group are referred to by an integer index in the range [0,n-1].) Following this are 2*n lines of data. The first n lines contain the preference lists for the elements of the first group. The first of these lines contains the preference list for element 0 of the first group. The next line contains the preference list for element 1 of the first group, and so forth. The next n lines contain the preference lists for the elements of the second group. The first of these lines contains the preference list for element 0 of the second group. The next line contains the preference list for element 1 of the second group, and so forth. Each line of data representing a preference list contains n numbers, separated by spaces. Specifically, it contains some permutation of the integers in the range [0,n-1]. The values are ordered from highest preference to lowest preference. You may assume all values fit in a 32-bit integer. Output specification: the output contains a single line, containing either the string "YES", or the string "NO", and ending with the end- of-line character ' '. The output should be "YES" if there two completely different stable matchings exist for this input. The output should be "NO" otherwise. Initialize each person to be free. while (some prof is free and hasn't asked every student) { Choose such a prof p s = 1st student on p's list whom p has not yet asked if (s is free) assign p and s to be partners else if (s prefers p to current partner p'). assign p and s to be partners, and p' to be free else s rejects p 31420 42013 10 4312 21034 14023 13240 02431 142310 30241 20314 YES