bzoj1143: [CTSC2008]祭祀river

选出来的点只能是不能向流通的，所以就是从n个点的二分图（相连通的连边）里面，选出最大独立集

const int N = 110;
int n, m;
bool Graph[N][N], Okay[N];
int Disx[N], Disy[N], Que[N], Head, Tail;
int Match[N], Vis[N];

inline void Input() {
	scanf("%d%d", &n, &m);
	Rep(i, m) {
		int x, y;
		scanf("%d%d", &x, &y);
		Graph[x][y] = 1;
	}
}

inline bool Bfs() {
	bool Flag = 0;
	Head = 0, Tail = 0;
	
	clr(Disx, 0), clr(Disy, 0);
	For(i, 1, n)
		if(!Okay[i]) Que[Tail++] = i;
	
	while(Head < Tail) {
		int x = Que[Head++];
		For(v, 1, n)
			if(Graph[x][v] && !Disy[v]) {
				Disy[v] = Disx[x] + 1;
				if(!Match[v]) Flag = 1;
				else Disx[Match[v]] = Disy[v] + 1, Que[Tail++] = Match[v];
			}
	}
	
	return Flag;
}

inline bool Find(int u) {
	For(v, 1, n)
		if(Graph[u][v] && Disy[v] == Disx[u] + 1) {
			Disy[v] = 0;
			if(!Match[v] || Find(Match[v])) {
				Match[v] = u, Okay[u] = 1;
				return 1;
			}
		}
	return 0;
}

inline void Solve() {
	/* Init Begin */
	For(k, 1, n)
		For(i, 1, n)
			For(j, 1, n)
				Graph[i][j] |= Graph[i][k] & Graph[k][j];
	/* Init End */
	
	int Ans = 0;
	while(Bfs())
		For(i, 1, n)
			if(!Okay[i]) Ans += Find(i);
	
	printf("%d\n", n - Ans);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1143");
	#endif
	Input();
	Solve();
	return 0;
}