복수전공

• 강의를 노드로, 겹치는 관계를 엣지로 연결해주자. 다른 학부의 강의들 사이에서만 엣지가 존재하기 때문에 이분 그래프가 된다.
• 겹치지 않는 강의들을 최대한 많이 고르는 것은 최대 독립집합을 구하는 문제가 되고, 전체 노드 갯수에서 최소 버텍스 커버의 크기를 빼주면 최대 독립집합의 크기를 구할수 있다. 이분그래프이기 때문에 쾨닉의 정리에 따라서 최소 버텍스 커버의 크기는 최대 매칭의 크기와 같다. 결국 답은 n에서 이분매칭의 크기를 빼주면 된다.
• 시간복잡도는 이분 매칭 (Bipartite Matching)을 구하는데에 O(VE)가 걸린다.

"""Solution code for "BOJ 12843. 복수전공".

- Problem link: https://www.acmicpc.net/problem/12843
- Solution link: http://www.teferi.net/ps/problems/boj/12843

Tags: [Bipartite Matching]
"""

import sys
from teflib import tgraph


def main():
    # pylint: disable=unused-variable
    n, m = [int(x) for x in sys.stdin.readline().split()]
    bigraph = [[] for _ in range(n)]
    comp_lectures = set()
    for _ in range(n):
        lecture, dep = sys.stdin.readline().split()
        if dep == 'c':
            comp_lectures.add(int(lecture))
    for _ in range(m):
        lecture1, lecture2 = [int(x) for x in sys.stdin.readline().split()]
        if lecture1 in comp_lectures:
            bigraph[lecture1 - 1].append(lecture2 - 1)
        else:
            bigraph[lecture2 - 1].append(lecture1 - 1)

    print(n - len(tgraph.bipartite_matching(bigraph)))


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.bipartite_matching