Factory

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

vector<int> g1[555];

int r[555][555];

int u[555];

int git=1;

void dfs(int x, int s){
	if (u[x]==git) return;
	r[s][x]=1;
	u[x]=git;
	for (int nx:g1[x]){
		dfs(nx, s);
	}
}

struct Matching{
	int n;
	vector<int> vLabel,ma,s,u;
	queue<int> q;
	void rm(int x, int y){
		int m=ma[x];ma[x]=y;
		if (ma[m]==x){
			if (vLabel[x]<=n){
				ma[m]=vLabel[x];
				rm(vLabel[x], m);
			}
			else{
				int a=1+(vLabel[x]-n-1)/n;
				int b=1+(vLabel[x]-n-1)%n;
				rm(a, b);
				rm(b, a);
			}
		}
	}
	void tr(int x){
		for (int i=1;i<=n;i++){
			s[i]=ma[i];
		}
		rm(x, x);
		for (int i=1;i<=n;i++){
			if (ma[i]!=s[i]) u[i]++;
			ma[i]=s[i];
		}
	}
	void rl(int x, int y){
		for (int i=1;i<=n;i++){
			u[i]=0;
		}
		tr(x);
		tr(y);
		for (int i=1;i<=n;i++){
			if (u[i]==1&&vLabel[i]<0){
				vLabel[i]=n+x+(y-1)*n;
				q.push(i);
			}
		}
	}
	int solve(vector<int>* g){
		for (int i=1;i<=n;i++){
			if (ma[i]==0){
				for (int j=1;j<=n;j++){
					vLabel[j]=-1;
				}
				vLabel[i]=0;
				q.push(i);
				while (!q.empty()){
					int x=q.front();
					q.pop();
					for (int y:g[x]){
						if (ma[y]==0&&i!=y){
							ma[y]=x;
							rm(x, y);
							while (!q.empty()) q.pop();
							break;
						}
						if (vLabel[y]>=0){
							rl(x, y);
							continue;
						}
						if (vLabel[ma[y]]<0) {
							vLabel[ma[y]]=x;
							q.push(ma[y]);
						}
					}
				}
			}
		}
		int res=0;
		for (int i=1;i<=n;i++) if (ma[i]>i) res++;
		return res;
	}
	Matching(int nn) : n(nn), vLabel(n+1), ma(n+1), s(n+1), u(n+1) {}
};

vector<int> g[555];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for (int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		g1[a].push_back(b);
	}
	for (int i=1;i<=n;i++){
		git++;
		dfs(i, i);
	}
	for (int i=1;i<=n;i++){
		for (int ii=i+1;ii<=n;ii++){
			if (r[i][ii]==0&&r[ii][i]==0){
				g[i].push_back(ii);
				g[ii].push_back(i);
			}
		}
	}
	Matching ma(n);
	int mm=ma.solve(g);
	assert(mm*2<=n);
	cout<<mm+n-mm*2<<endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED