[12843] 복수전공

어휴.. 엄청 어렵네요..

이분 매칭일 것이라고 생각은 했는데

어떻게 적용해야할까?가 문제였습니다.

중복되는 강의를 제외하고 어떻게 연결을 하지.. 라는 엄청난 고민...

나는 바보였다!!!!!!!!!!!!...

중복된 과목끼리 선을 만들어서 N개의 과목 - 중복된 과목 을 하면 정답이 나오는 것을...

역발상인거 같아요!!

무언가 풀다가 막히면 항상 거꾸로 역발상하는 방법도 생각해보는 것도 좋을 것 같습니다.

중복을 피하는 것이 아닌 중복을 찾는다...

어려웠습니다...

후!

그걸 제외하고는 다른 이분매칭과 다르지 않습니다.

이분 매칭을 리마인드하기 좋은 문제였습니다..

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
 
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int> >
#define vll vector<ll>
 
#define MOD 86400
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
int n, m;
 
vi edge[2001];
bool visit[2001];
 
int A[2001];
int B[2001];
 
vi vi_left;
 
bool f(int idx) {
    visit[idx] = 1;
 
    for (int i = 0; i < edge[idx].size(); i++) {
        int to = edge[idx][i];
 
        if (!B[to] || (!visit[B[to]] && f(B[to]))) {
            B[to] = idx;
            A[idx] = to;
 
            return 1;
        }
    }
 
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        int a;
        char major;
 
        cin >> a >> major;
        
        if (major == 'c') {
            vi_left.push_back(a);
        }
    }
 
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
 
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
 
    int ret = n;
 
    for (int i = 0; i < vi_left.size(); i++) {
        memset(visit, 0, sizeof(visit));
 
        ret -= f(vi_left[i]);
    }
 
    cout << ret;
 
    return 0;
}