最大マッチング(PHP)

	// maximum matching algorithm
	// unweighted bipartite graph
	// dfs hungarian algorithm

	function dfs($bigraph, $u, &$path, &$matching){
		foreach($bigraph[$u] as $v){
			if(!isset($path[$v])){		// not in path already
				$path[$v] = true;
				if(!isset($matching[$v]) || dfs($bigraph, $matching[$v], $path, $matching)){
					// not matching node, the path is agumenting path, switch path, and return true
					$matching[$v] = $u;
					$matching[$u] = $v;
					return true;
				}
			}
		}
		
		return false; 					// not agumenting path
	}
	
	function hungarian($bigraph){
		$matching = [];

		foreach($bigraph as $u=>$x){
			if(!isset($matching[$u])){	// not a matching node
				$path = []; 			// save the nodes in path
				dfs($bigraph, $u, $path, $matching);
			}
		}
		
		return array_intersect_key($matching, $bigraph);
	}

	// left node idx is key
	// right nodes is value
	// eg. left nodes: 0 - 4, right nodes = 5 - 9
	$bigraph = [0 => [6, 9], 1 => [7], 2 => [6, 8], 3 => [8, 9], 4 => [5, 7]];
	$r = hungarian($bigraph);
	print_r($r);
?>