increase the efficiency of a matching algorithm
1. The Hopcroft–Karp algorithm

The problem you're trying to solve here is to find a maximum matching in an unweighted bipartite graph. This can be solved in \$O(\sqrt V E)\$ by the Hopcroft–Karp algorithm.

Here's a sketch of how the Hopcroft–Karp algorithm works. Suppose that we have a bipartite unweighted graph, like the one you use as an example in the post:



Because it's bipartite, there are two sets of vertices which we'll call \$U\$ and \$V\$:



The Hopcroft–Karp algorithm works by repeatedly augmenting the matching, increasing the number of edges in the matching by one. Suppose that we have added one edge to the matching so far, between \$y\$ and \$2\$, drawn as a red edge:



The algorithm now searches for an augmenting path. This is a path that starts at an unmatched vertex in \$U\$, crosses to \$V\$ on an unmatched (black) edge, crosses back to \$U\$ on a matched (red) edge, and so on, finally ending in \$V\$. Here's an augmenting path, starting at \$x\$, following an unmatched edge to \$2\$, following a matched edge to \$y\$, and following an unmatched edge to \$3\$:



An augmenting path has an odd number of edges (because it starts in \$U\$ and finishes in \$V\$) and the edges along the path alternate between unmatched and matched. This means that if we swap all the edges along the augmenting path (matched becoming unmatched and vice versa), we get a new matching with one more edge, like this:



Now carrying on with the algorithm, there is another augmenting path, \$z\$–\$2\$–\$x\$–\$1\$:



Swapping the edges along this path, we increase the matching again:



Now there are no more augmenting paths (because there are no unmatched vertices in \$U\$) and we are done.

How do we find the augmenting paths? Well, we use a combination of breadth-first search and depth-first search. At each stage we do a breadth-first search to divide the vertices into layers according to their shortest distance from an unmatched vertex along an augmenting path. Suppose we are at this stage of the algorithm, where \$y\$ has been matched with \$2\$:



Now the breadth-first search divides the vertices into the following layers:



Using this structure, an augmenting path can be found efficiently (linear time) by a depth-first search that only follows edges from lower-numbered layers to higher-numbered layers.

2. Implementation

This is a direct translation of the pseudocode from Wikipedia into Python. To help with book-keeping, this implementation introduces a distinguished node nil, with all vertices being artificially matched with nil to start with. When there are no more augmenting paths ending at nil then we know the matching is maximal.

from collections import deque

def maximum_matching(graph):
    """Find a maximum unweighted matching in a bipartite graph. The input
    must be a dictionary mapping vertices in one partition to sets of
    vertices in the other partition. Return a dictionary mapping
    vertices in one partition to their matched vertex in the other.

    """
    # The two partitions of the graph.
    U = set(graph.keys())
    V = set.union(*graph.values())

    # A distinguished vertex not belonging to the graph.
    nil = object()

    # Current pairing for vertices in each partition.
    pair_u = dict.fromkeys(U, nil)
    pair_v = dict.fromkeys(V, nil)

    # Distance to each vertex along augmenting paths.
    dist = {}
    inf = float('inf')

    def bfs():
        # Breadth-first search of the graph starting with unmatched
        # vertices in U and following "augmenting paths" alternating
        # between edges from U-&gt;V not in the matching and edges from
        # V-&gt;U in the matching. This partitions the vertexes into
        # layers according to their distance along augmenting paths.
        queue = deque()
        for u in U:
            if pair_u[u] is nil:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = inf
        dist[nil] = inf
        while queue:
            u = queue.pop()
            if dist[u] &lt; dist[nil]:
                # Follow edges from U-&gt;V not in the matching.
                for v in graph[u]:
                    # Follow edge from V-&gt;U in the matching, if any.
                    uu = pair_v[v]
                    if dist[uu] == inf:
                        dist[uu] = dist[u] + 1
                        queue.append(uu)
        return dist[nil] is not inf

    def dfs(u):
        # Depth-first search along "augmenting paths" starting at
        # u. If we can find such a path that goes all the way from
        # u to nil, then we can swap matched/unmatched edges all
        # along the path, getting one additional matched edge
        # (since the path must have an odd number of edges).
        if u is not nil:
            for v in graph[u]:
                uu = pair_v[v]
                if dist[uu] == dist[u] + 1: # uu in next layer
                    if dfs(uu):
                        # Found augmenting path all the way to nil. In
                        # this path v was matched with uu, so after
                        # swapping v must now be matched with u.
                        pair_v[v] = u
                        pair_u[u] = v
                        return True
            dist[u] = inf
            return False
        return True

    while bfs():
        for u in U:
            if pair_u[u] is nil:
                dfs(u)
    return {u: v for u, v in pair_u.items() if v is not nil}