Sogang Programming Contest Champion 2013 책 나눠주기 January 03, 2014

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <string>
using namespace std;
#define MAX_V 1004
const int inf = 987654321;
vector<vector<int> > v;
int N,M;
int backMatch[MAX_V*2+5];
bool visited[MAX_V*2+5];
bool dfs(int now) {
    if ( visited[now] ) return false;
    visited[now] = true;
    for ( int i = 0 ; i < v[now].size() ;i ++ ) {
        int next = v[now][i];
        if ( backMatch[next] == -1 || dfs(backMatch[next] ) ) {
            backMatch[next] = now;
            return true;
        }
    }
    return false;
}
int matching() {
    memset(backMatch,-1,sizeof(backMatch));
    int matched = 0;
    for ( int i = 0 ; i < v.size() ; i++ ) {
        memset(visited,false,sizeof(visited));
        if ( dfs(i) ) matched++;
    }
    return matched;
}
int main() {
    int tc;
    scanf("%d",&tc);
    while ( tc-- ) {
        scanf("%d%d",&N,&M);
        v.resize(M+10);
        for ( int i = 0 ; i < M ; i++ ) {
            int a,b;
            scanf("%d%d",&a,&b);
            a--; b--;
            for ( int j = M+a ; j <= M+b ; j++ )
                v[i].push_back(j);
        }
        printf("%d\n",matching());
        for ( int i = 0 ; i < v.size() ; i++ )
            v[i].clear();
        v.clear();
    }
    return 0;
}