pku1778.java

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· Java 代码 · 共 98 行

#include <stdio.h>
#include <string.h>
#define SIZE 51000
typedef struct Node
{
	int id;
	int next;
} Node;

Node G[SIZE * 4];
int G_end;
int N1, N2, D;
int IN[SIZE * 2], in[SIZE * 2];
int S[2][SIZE];
int top[2];

int F(int x)
{
	return x > N1 ? 1 : 0;
}

void Insert(int x, int y)
{
	int p = y;
	while (G[p].next)
		p = G[p].next;
	G[p].next = G_end;
	p = G[p].next;
	G_end++;
	G[p].id = x;
	IN[x]++;
}

int check(int x)
{
	int cnt, i, j, pos, p, id;
	top[0] = 0;
	top[1] = 0;
	for (i = 1; i <= N1 + N2; i++)
	{
		in[i] = IN[i];
		if (in[i] == 0)
		{
			S[F(i)][top[F(i)]++] = i;
		}
	}
	pos = x;
	cnt = 0;
	while (1)
	{
		if (!top[0] && !top[1])
		{
			break;
		}
		if (!top[pos % 2])
		{
			pos++;
		}
		cnt++;
		top[pos % 2]--;
		p = S[pos % 2][top[pos % 2]];
		while (G[p].next)
		{
			p = G[p].next;
			id = G[p].id;
			in[id]--;
			if (in[id] == 0)
				S[F(id)][top[F(id)]++] = id;
		}
	}
	return pos - x;
}

void Solve()
{
	int i, x, y;
	int ans, tmp;
	memset(G, 0, sizeof(G));
	memset(IN, 0, sizeof(IN));
	G_end = SIZE * 2;
	for (i = 0; i < D; i++)
	{
		scanf("%d %d", &x, &y);
		Insert(x, y);
	}
	ans = check(0);
	tmp = check(1);
	if (tmp < ans)
		ans = tmp;
	printf("%d\n", ans + 2);
}

int main()
{
	while (EOF != scanf("%d %d %d", &N1, &N2, &D) && (N1 + N2 + D))
		Solve();
	return 0;
}