Source Code
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define md ((st + nd) >> 1)
#define lc (1 + (idx << 1))
#define rc (2 + (idx << 1))
const int N = 100005;
vector <int> v[N], g[N];
int ans[N];
bool vis[N];

int main() {
	int n, m, k;
	scanf("%d %d %d", &n, &m, &k);
	int res = 0;
	for (int i = 0; i < k; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		v[y].pb(x);
		g[x].pb(y);
	}
	for (int i = 1; i <= n; i++) {
		res += (int)g[i].size() > 0;
	}
	int hold = res;
	multiset <int> mst;
	for (int i = 1; i <= m; i++) {
		for (int y : v[i]) {
			ans[i] += (int)g[y].size() == 1;
		}
		mst.insert(ans[i]);
		res = min(res, hold + 1 - ans[i]);
	}
	for (int i = 1; i <= m; i++) {
		mst.erase(mst.find(ans[i]));
		map <int, int> mp;
		for (int y : v[i]) {
			if ((int)g[y].size() != 2) continue;
			int x = g[y][0];
			if (x == i) x = g[y][1];
			mp[x]++;
			mst.erase(mst.find(ans[x]));
		}
		if ((int)mst.size()) {
			res = min(res, hold + 2 - ans[i] - *mst.rbegin());
		}
		for (auto x : mp) {
			mst.insert(ans[x.fi]);
			res = min(res, hold + 2 - ans[i] - ans[x.fi] - x.se);
		}
		mst.insert(ans[i]);
	}
	printf("%d", res);
	return 0;
}
Copy
Min Vertex Cover 2 aboAdnan
GNU G++17
64 ms
6.8 MB
Runtime Error