공유하고자 메모 남겨둡니다.
edgeList에 홀수 혹은 짝수(첫번째 입력값이랑 같은 종류의 수들)가 모두 추가 되지 않은 경우 저러한 방식을 보장할 수 없었습니다.
ex) N = 4
입력값으로 2 3 6 9 된 경우
edgeList에는
2 ->3, 9 가 추가되고
(6->0, ※ 이부분이 추가되었어야 했는데 그러질 못했네요. )
6은 빠져있는 상태에서 true, false를 판단하게되고,
결국 잘못된 결과가 나오네요.
즉, 하나의 원소라도 edgeList에서 빠져있으면, 그 원소를 빼고 dfs를 이용한 이분 매칭을 시도하니깐
그 원소는 고려 안하고 나머지만 고려해서 true인지 false인지 판별하네요...
그래서 매칭이 되는 쌍을 셀 수 밖에 없었던 거네요
만약에 true, false를 이용하고 싶다면, edgeList에 첫번째 입력값이랑 같은 종류(홀수 혹은 짝수)의 입력값을 모두 추가해주면 될 거 같습니다.
ther203 6년 전
대부분이 아시다시피 짝 홀수 나누어서 이분매칭으로 풀었는데요...
여기서 edegelist는 이분매칭을 하기 위해 필요한 짝홀수간 연결 상태(즉 더해서 소수가 되는 상태)를 나타내는 데이터 구조입니다.
가량 {4,5,7,10,11,12}가 입력된 경우 edgelist는
4->7
10->7
12->5,7,11
로 만들어집니다.
makeMatchingList 함수에서
vector<int>::iterator firstIt = edgeList[first].begin();
while (firstIt != edgeList[first].end()) {
map<int, int> matchingPair;
bool flag = true;
map<int, vector<int>>::iterator mit = edgeList.begin();
while (mit!=edgeList.end()) {
if (mit->first != first) {
map<int, int> visited;
if (!PairMatching(*firstIt, mit->first, edgeList, visited, matchingPair)) {
flag = false;
break;
}
}
mit++;
}
if (flag) {
matchingList.push_back(*firstIt);
}
firstIt++;
}
vector<int>::iterator firstIt = edgeList[first].begin();
while (firstIt != edgeList[first].end()) {
map<int, int> matchingPair;
int flag = 1;
map<int, vector<int>>::iterator mit = edgeList.begin();
while (mit!=edgeList.end()) {
if (mit->first != first) {
map<int, int> visited;
if (PairMatching(*firstIt, mit->first, edgeList, visited, matchingPair)) flag++;
}
mit++;
}
if (flag==num/2) matchingList.push_back(*firstIt);
firstIt++;
}
(이 때 num은 총 입력의 갯수 N과 같습니다.)
위와 같이 수정하면 됩니다.
이분 매칭에서 중간에 한 번이라도 짝을 못 찾는 경우가 있으면
짝을 못 찾은 값은 뒤에 진행상황에 관계없이 짝이 없는 거 아닌가요???