이분 매칭이 어떤 원리로 동작되는 알고리즘인가요?

구현이 잘못되었는데요.

이분 매칭이 어떤 알고리즘인지 볼게요. 보통 쉽게 재귀적으로 구현하는 알고리즘의 경우에..

(1) 어떠한 녀석 aa가 어떠한 친구랑 Matching을 하려고 해요. 그러면 후보해는 con[aa]의 원소 중 하나겠죠?

그러면, AA -> BB가 Matching이 되었다는 건 어떻게 판단하죠? 역간선 정보를 주면 됩니다. rev[bb] = aa; 이런 식으로

어떠한 aa에 대해서

(1) 일단 aa와 연결이 되어 있는 간선을 찾고.

(2) 그 간선이 다른 친구로부터 연결이 되어 있는지, 안 되어 있는지를 재귀적으로 찾으면서

(3) 만약에 비어 있는 게 있으면 연결 시켜주고 return 시켜주는 거죠.

그러한 구현이 보이지 않네요.

반례는 못 찾아드리겠지만, 이분 매칭 구현도 아니고, 재귀적으로 dfs를 찾는 것도 아니네요.. 레벨 간선 줘서 어떻게 한 건지는 잘 모르겠는데 아닌 거 같아요.

bfs 코드도 안 보이고 dfs 코드도 안 보이고..

코드 쭉 읽어보니까 visit_ground[yy] 는 ?? -> yy로부터 이어지는 간선이 있는가? 를 나타낸 거 같은데.. 이 ??가 없으면 0이네요.

일단 아래 테케에서 반례가 나오고요.. 아니 그 전에 visit_ground[uu]가 어떤 의미인가요?

대충 코드 보니까..

의문점이 몇 가지 더 있는데요. 왜 굳이 backtracking의 리턴 값이 int형 array type으로 하셨나요? 그렇게 한 이유가 있나요?

backtracking 함수가 호출되었을 때 메모리에 객체들이 어떻게 올라가는지 그려 보셨나요..?

Java에서 2차원 배열이 할당되면 어떤 식으로 메모리에 올라가는지 그려보세요.. 이 개념도 헷갈리시는 거 같아요..