New Shops

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int MN = 555;
vector<int> v[MN];
vector<int> v2[MN];
bool used[MN];
void f(int x, vector<int> & w) {
	used[x] = 1;
	for(auto y: v[x]) {
		if(!used[y]) {
			f(y, w);
		}
	}
	w.push_back(x);
}
int qq[MN];
void f2(int x, int id) {
	used[x] = 1;
	qq[x] = id;
	for(auto y: v2[x]) {
		if(!used[y]) {
			f2(y, id);
		}
	}
}
bool v3[MN][MN];
int inD[MN];
int outD[MN];
bool vf[MN][MN];
int sz = 0;
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);
			}
		}
	}
	vector<pair<int, 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]);
						}
					}
				}
			}
		}
		vector<pair<int, int> > res;
		for (int i=1;i<=n;i++) if (ma[i]>i) res.push_back({i, ma[i]});
		return res;
	}
	Matching(int nn) : n(nn), vLabel(n+1), ma(n+1), s(n+1), u(n+1) {}
};
bool ff(int x) {
	if(x == 503) return 1;
	used[x] = 1;
	if(!used[503] && vf[x][503]) {
		bool q = ff(503);
		if(q) {
			vf[x][503] = 0;
			vf[503][x] = 1;
			return 1;
		}
	}
	for(int i = 0; i < sz; ++i) {
		if(!used[i] && vf[x][i]) {
			bool q = ff(i);
			if(q) {
				vf[x][i] = 0;
				vf[i][x] = 1;
				return 1;
			}
		}
	}
	return 0;
}
int main() {
	int n,m;
	cin>>n>>m;
	vector<pair<int, int> > edges;
	for(int i = 0; i < m; ++i) {
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
		v2[b].push_back(a);
		edges.push_back({a, b});
	}
	vector<int> jo;
	for(int i = 1; i <= n; ++i) {
		if(!used[i]) {
			f(i, jo);
		}
	}
	memset(used, 0, sizeof used);
	for(int i = jo.size()-1; i >= 0; --i) {
		int x = jo[i];
		if(!used[x]) {
			f2(x, sz);
			++sz;
		}
	}
/*
	for(int i = 1; i <= sz; ++i) {
		cout<<i<<' '<<qq[i]<<'\n';
	}
	cout<<'\n';
	*/
	for(int i = 0; i < m; ++i) {
		int a = qq[edges[i].F];
		int b = qq[edges[i].S];
		if(a != b) {
			++outD[a];
			++inD[b];
			v3[a][b] = 1;
		}
	}
	for(int i = 0; i < sz; ++i) {
		for(int j = 0; j < sz; ++j) {
			for(int k = 0; k < sz; ++k) {
				v3[j][k] |= (v3[j][i] & v3[i][k]);
			}
		}
	}
	vector<int> * v4;
	v4 = new vector<int>[555];

	for(int i = 0; i < sz; ++i) {
		for(int j = 0; j < sz; ++j) {
			if(v3[i][j]) {
				v4[i+1].push_back(j+1);
			}
		}
	}
	Matching ma(sz);
	auto q = ma.solve(v4);
	//cout<<q.size()<<'\n';
	cout<<sz-q.size()<<endl;
	return 0;
	int ans = 0; 
	memset(used, 0, sizeof used);
	for(int i = 0; i < sz; ++i) {
		if(outD[i] == 0 && inD[i] == 0) {
			++ans;
			used[i] = 1;
		}
	}
	int totSz = 0;

	for(int i = 0; i < sz; ++i) {
		//cout<<inD[i]<<' '<<outD[i]<<'\n';
		if(used[i]) continue;
		if(outD[i] == 0) {
			vf[i][503] = 1;
			++totSz;
			//cout<<"pois "<<i<<endl;
			for(int j = 0; j < sz; ++j) {
				if(j == i) continue;
				if(v3[j][i] && !used[j]) {
			//		cout<<"kaari "<<j<<' '<<i<<'\n';
					vf[j][i] = 1;
				}
			}
		}
		else if(inD[i] == 0) {
			vf[502][i] = 1;
			//cout<<"sisaan "<<i<<endl;
			++totSz;
			for(int j = 0; j < sz; ++j) {
				if(j == i) continue;
				if(v3[i][j] && !used[j]) {
					//cout<<"kaari "<<i<<' '<<j<<'\n';
					vf[i][j] = 1;
				}
			}
		}
	}
	int flow = 0;
	while(1) {
		memset(used, 0, sizeof used);
		int q = ff(502);
		if(q == 0) break;
		flow += q;
	}
	cout<<ans + totSz - flow<<'\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER