https://www.acmicpc.net/problem/1298전형적인 이분매칭 문제입니다.해당 알고리즘은 DFS 를 기반으로 합니다.우선 순차적으로 노드를 순회하며 매칭 가능한 노드를 연결합니다.다음 노드에서 임의의 노드를 골랐는데 해당 노드가 이미 다른 노드와 연결되어있다면 연결된 노드를 다른 노드와 연결시킬 수 있는지 재귀적으로 탐색하며 최대한 옮긴 뒤 현재의 노드와 고른 노드를 연결시키는 방식입니다.조금 가볍게 말하자면 지하철을 탔을 때 임의의 자리에 앉고 싶을 경우 이미 앉아있는 승객에게 양해를 구해 다른 자리로 옮기게 하는 방식이라고 할 수 있습니다.import sysfrom collections import dequeinput = sys.stdin.readline# 이분 매칭def bima..