Problem Link - The Bickering Task Force
Problem Statement
We meet our old friend the Despotic King again. The king was no believer in democracy (understandably) and did not wish to share any information regarding the running of his country even with the nobles in his court. He had an inner circle (a cabal) consisting of a few old friends from his youth and a couple of protégés and ran the kingdom with their help. It was, however, a benevolent dictatorship and thus there was hardly a protest either in the court or among the subjects.
The king’s sons and potential successors were, however, of dubious attitude and quality. Clearly, dictatorship of the incompetent was the future of the country if the king were to abdicate or die. Some of the younger nobles banded together and confronted the king and demanded openness.
The king promised to appoint a Task Force with members selected from among the nobles to oversee the administration of the country. However, he wished to choose its members in such a way that they would waste all their time fighting each other, leaving them no opportunity to introduce any changes in the way the country was being run.
His able advisor, the wily prime minister, gave him a list of all the pairs of nobles who hated each other. The king then wanted the minister to pick as large a Task Force as possible (so that his generosity was evident), in such a way that each member of the Task Force hates at least K other members (where K was a number to be determined by the king). The Task Force cannot be empty.
Note that whenever a pair of nobles “A and B” appears in the prime minister’s list, it means that A hates B and, symmetrically, B hates A.
Approach
The problem is solved by identifying the largest group of nobles where each member hates at least k others. We first count how many people each noble hates and remove those who hate fewer than k. After filtering, the remaining nobles are represented as a graph, with edges showing mutual hatred. Using union-find, we group connected nobles and determine the size of each group. The largest group satisfying the condition is the answer. If no group exists, we output “NO”; otherwise, we output “YES” with the group size. The BFS or DFS ensures efficient traversal and updates of the graph during filtering.
Time Complexity
The time complexity is O(n + m), where n is the number of nobles and m is the number of hatred pairs.
Space Complexity
The space complexity is O(n + m) for storing the graph and union-find structures.