1666.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 55 行

/*  This Code is Submitted by wywcgs for Problem 1666 on 2006-09-01 at 13:17:59 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 102400;
const int INF = 1 << 30;

vector<int> g[N];
int d[2][N], n1, n2;

int install(int);

int main()
{
	int m;

	while(scanf("%d %d %d", &n1, &n2, &m) != EOF && n1 != 0) {
		memset(d, 0, sizeof(d));
		for(int i = 0; i < n1+n2; i++) g[i].clear();
		for(int i = 0; i < m; i++) {
			int a, b; scanf("%d %d", &a, &b); a--; b--;
			g[a].push_back(b); d[0][b]++; d[1][b]++;
		}
		int best = INF;
		for(int i = 0; i < 2; i++) best <?= install(i);
		printf("%d\n", best+1);
	}
	
	return 0;
}

int install(int k)
{
	int cn = 0, stack[2][N>>1], top[2] = { 0 };
	for(int i = 0; i < n1+n2; i++)
		if(d[k][i] != 0) continue;
		else if(i < n1) stack[0][top[0]++] = i;
		else stack[1][top[1]++] = i;
	if(top[k] == 0) return INF;
	for(int i = k; top[i] != 0; i = 1-i, cn++) {
		while(top[i] != 0) {
			int p = stack[i][--top[i]];
			for(int j = g[p].size()-1; j >= 0; j--) {
				int o = g[p][j]; d[k][o]--;
				if(d[k][o] != 0) continue;
				int ko = (o >= n1);
				stack[ko][top[ko]++] = o;
			}
		}
	}
	return cn;
}