[백준]노트북의 주인을 찾아서(1298)

문제 링크 : [백준]노트북의 주인을 찾아서(1298)

문제 설명

N명의 사람에 대하여 자신의 노트북인 것 같은 후보들을 지정합니다.
후보는 M개가 주어지며, 이때 최대한 많은 사람에게 자신이 후보로 지정한 노트북을 갖게 해주고싶습니다.
최대한 많은 사람에게 노트북을 줄 때, 몇명의 사람에게 노트북을 줄 수 있는지 구하세요.

입력

N(사람의 수, 1 <= N <= 100)
M(후보의 수, 1 <= M <= 5,000)
A_i B_i(A_i 사람이 B_i 노트북이 자신의 것 같다고 주장)

5 5
1 1
2 2
3 3
4 4
5 5

출력

5

카테고리

#이분매칭

시간 복잡도 상한

O(N⁴)

해결 방법

1. 사람 -> 노트북으로 이루어지는 이분 그래프가 형성됩니다.
2. 이분 그래프에서 최대한 많은 연결 관계를 이루어야하기 때문에 이분매칭을 이용하여 최대 연결 수를 구합니다.

시간복잡도

O(N*M)

코드

#include<cstdio>
#include<string.h>
#define N 101
using namespace std;
int n,m,d[N],v[N],a,b,c[N][N];
int r(int p){
    if(v[p])return 0;
    v[p]=1;
    for(int x:c[p]){
        if(x&&(!d[x]||r(d[x]))){
            d[x]=p;
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    while(m--){
        scanf("%d%d",&a,&b);
        c[a][b]=b;
    }
    for(b=0,a=1;a<=n;a++){
        memset(v,0,sizeof(v));
        b+=r(a);
    }
    printf("%d",b);
}