Untitled
raw download clone
CPP
views 13
,
size 1413 b
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define ms(a, b) memset(a, b, sizeof(a))
#define ALL(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
constexpr ll MOD = 1e9 + 7;

vector<vector<int>> adj;
vector<int> matched;
vector<bool> check;
bool dfs(int u) {
	for(auto& v : adj[u]) if(!check[v]){
		check[v] = 1;
		if(matched[v] == -1 || dfs(matched[v])) {
			matched[v] = u;
			matched[u] = v;
			return true;
		}
	}
	return false;
}

inline void solve() {
	int n, m; cin >> n >> m;
	adj.assign(n + 1, vector<int>(n + 1));
	matched.assign(n + 1, -1);
	while(m--) {
		int a, b; cin >> a >> b;
		adj[a].eb(b);
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		if(matched[i] == -1) {
			check.assign(n + 1, 0);
			if(dfs(i))
				ans++;
		}
	}
	cout << ans << '\n';
}

//#define IOFILE
int main() {
#ifndef IOFILE
	cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);
#endif
#ifdef IOFILE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("err.txt", "w", stderr);
	clock_t time = clock();
#endif
	int t = 1;
	cin >> t;
	while(t--) {
		solve();
	}

#ifdef IOFILE
	cout << "\nUse " << static_cast<double>(clock() - time) / CLOCKS_PER_SEC << " seconds";
#endif
}
close fullscreen
Login or Register to edit or fork this paste. It's free.