This challenge is extremely interesting because it can be applied to many fields in game development and, a bit modified of course, also to a diversity of other problem that rely on grouping users together. The idea is to use the concept of coloring graphs to find groupings for multiplayer games. So to fully understand this, you should probably be familiar with bipartite graph coloring. If you need to freshen up on this topic i recommend you the following resource which explains it quite clearly:

Ok! Now that we are ready, let’s dive right into the challenge. The problem description is as follows:

You are developing a matchmaking system for your online game and you prioritize that strangers play against each other. This means that if two players and are not friends, then they should be in opposite teams. Since you want some diversity you’ll allow that friends are grouped in different teams (So two strangers are always in different teams while two friends might be). Develop an algorithm that determines wheter such a grouping is possible given the needed friendship informations.

• Input:
• The first line contains three integers , denoting the number of people attending in the game, the total number of “not friends” relations and a player ID.
• The next lines each contain two integers , indicating that the player is not friends with person . (You can assume that friendships are symmetric, so if is not friends with then is also not friends with )
• Output:
• Output a list of player ID’s that are in the opposite team of ordered increasingly, or “ ” if a matchmaking with the given properties is not possible
• Constraints:
• Your algorithm should have a time complexity of Now that we have a task let’s start working on a solution. As i’ve already hinted such a problem can be solved using bipartite graph coloring. Let us first define how we model a graph from the given data:

Let be an undirected and unweighted graph as follows:

• Every player of our game is represented by a distinct node in . So we have

begin{align*}
|V| = k
end{align*}

• Two nodes are connected with an edge, exactly if the player represented by is not friends with the player represented by . So we have

begin{align*}
forall x,y in V(e=(x,y) in E Leftrightarrow x text{ is not friends with } y)
end{align*}
and

begin{align*}
|E| = l
end{align*}

The trick is now that a biparite partition of corresponds exactly to a grouping that we want. And here’s why:

By the definition of a bipartite partition , we have

begin{align*}
forall x,y in A nexists e=(x,y) in E ;;; text{and} ;;; forall x,y in B nexists e=(x,y) in E
end{align*}
so grouping the players into the two groups and assures us that no two players who are not friends are in the same group (otherwise there would be an edge between them and thus wouldn’t be a bipartition).

Perfect! Everything that’s left is an implementation. As always i’ll solve this problem in java. The same concepts will of course work just as well with other languages. First of all we need to implement a function that partitions a given graph into a bipartition. We can use a modified Breadth-First-Search to do this. Basically we start at some node and give it a color. All it’s neighbours will be colored differently and so on. This way we color the graph layer by layer and we can even check if a bipartition is possible (as soon as we can not color a node differently from its neighbours we can simply return ).

``````/**
* Performs a bipartit partitioning on a given graph
* @param source start node of bfs
* @param coloring partition array
* @return true if partition was possible, false if not. Partition itself is stored in coloring array
*/

//Start bfs from node 0
coloring[source] = 1;

//Perform bfs from 0
while(queue.size() > 0) {
int s = queue.removeFirst();
if(coloring[neighbour] == 0) {
if(coloring[s] == 1) {coloring[neighbour] = 2;}
else {coloring[neighbour] = 1;}
}
//If neighbour must have the same color as source then not bipartit
else if(coloring[neighbour] == coloring[s]) {
return false;
}

}
}

//Repeat for potentially remaining other connected components
for(int i = 0; i < coloring.length; i++) {
if(coloring[i] == 0) {return partitioningBfs(i, adjList, coloring);}
}

//At this point we have partitioned the graph sucessfully, so return true
return true;

}``````

Next we need a function that builds a list of players according to the output specification. As we’ve seen an opponent of a player is in the opposite partition, so we can traverse the array and add all players colored differently than our given player to a list, sort said list and return it. Should a bipartition not be possible, we simply return .

`````` /**
* Check if it is possible to group all non-friends in opposite teams.
* @param adjList A graph that represents non-friendship between the players
* @param opp the player whose opponents should be in the list
* @return a list of players that are not in the same team as the given player,
* empty list if matchmaking is not possible
*/
int[] coloring = new int[adjList.length]; //Stores the partition of a node [0 is unpartitioned]

//Partitioning successful, build list
int playPart = coloring[opp];
for(int i = 0; i<coloring.length; i++) {
if(coloring[i] != playPart) {
}
}

//Sort list in ascending order
Collections.sort(out);

//Return list
return out;

} else { return new LinkedList<Integer>(); }
}``````

Finally all that’s left is handling I/O by building a graph from the input and outputting either the list elements or “ ``````private static int m;

public static void testCase() {
getAndStoreUserInput();
}

private static void getAndStoreUserInput() {
Scanner scanner = new Scanner(System.in);

int k = scanner.nextInt();
int l = scanner.nextInt();
m = scanner.nextInt();

for(int i = 0; i<k; i++) {
}

for(int i = 0; i<l; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();

}

scanner.close();
}

StringBuilder str = new StringBuilder();
for(int opponendID: opponents) {
str.append(opponendID + " ");
}
String builtString = str.toString();
String out = builtString.equals("") ? "false": builtString;
System.out.println(out);
}``````

Runtime analysis:
Building the graph from input takes (since we have two loops with constant body, one takes and one iterations). Building the output takes since there can not be more opponents than players. Building the opponent list takes since we have to iterate once through the array which has as many items as has nodes. Last but not least we perform our modified bfs exactly once on the graph. Our modifications did not change the runtime of bfs and bfs is known to run in . So our total runtime is:

begin{align*}
O(k+l) + O(k) + O(k) + O(k+l) = O(4k + 2l) = O(k + l)
end{align*}
Which means that we have met the runtime requirements