1087.cc

北大ACM网站 1087题 http://acm.pku.edu.cn/JudgeOnline/problem?id=1087

#include <map>
#include <stack>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;

typedef struct node
{
	int ord;
	node * next;
}Node;

const int size = 512 + 1;

Node	list[size];
int	X[size];
int	Y[size];
bool	visit[size];
int	size_x;
int	size_y;
int	total = 0;
int	mm[401][401] = {0};
stack	<int>	stk;

void init()
{
	int i;

	for (i = 1; i <= size_x; i++)
		list[i].next = NULL;
	memset(X, 0, (size_x + 1) * sizeof(int));
	memset(Y, 0, (size_y + 1) * sizeof(int));
}

void input()
{
	int i, j, x, y;
	int dev[401];
	Node* p;
	string t, s;
	map <string, int> mp;

	scanf("%d", &size_x);
	for (i = 1; i <= size_x && cin >> s; i++)
	{
		mp[s] = ++total;
		mm[i][i] = 1;
	}
	scanf("%d", &size_y);
	for (i = 1; i <= size_y && cin >> t >> s; i++)
	{
		if (!mp[s]) mp[s] = ++total;
		dev[i] = mp[s];
	}
	scanf("%d", &i);
	while (i-- && cin >> t >> s)
	{
		if (!mp[t]) mp[t] = ++total;
		if (!mp[s]) mp[s] = ++total;
		mm[mp[s]][mp[t]] = 1;
	}
	for (x = 1; x <= total; x++)
		for (i = 1; i <= total; i++)
			for (j = 1; j <= total; j++)
				if (mm[i][x] && mm[x][j])
					mm[i][j] = 1;
	for (x = 1; x <= size_x; x++)
		for (i = 1; i <= total; i++)
		{
			if (!mm[x][i]) continue;
			for (y = 1; y <= size_y; y++)
			{
				if (dev[y] != i) continue;
				p = new Node;
				p->ord = y;
				p->next = list[x].next;
				list[x].next = p;
			}
		}
}

bool dfs(int x)
{
	Node* p;

	stk.push(x);
	for (p = list[x].next; p; p = p->next)
		if (!visit[p->ord])
		{
			visit[p->ord] = true;
			stk.push(p->ord);
			if (!Y[p->ord] || dfs(Y[p->ord]))
				return true;
			else
				stk.pop();
		}
	stk.pop();

	return false;
}

void solve()
{
	int i, top;

	for (i = 1; i <= size_x; i++)
	{
		while (!stk.empty()) stk.pop();
		memset(visit, false, size_y + 1);
		if (dfs(i))
			while (!stk.empty())
			{
				top = stk.top();
				stk.pop();
				Y[top] = stk.top();
				X[stk.top()] = top;
				stk.pop();
			}
	}
}

void output()
{
	int i, count = 0;
	Node*	p;

	for (i = 1; i <= size_x; i++)
	{
		if (X[i]) count++;
		while (p = list[i].next)
		{
			list[i].next = p->next;
			delete p;
		}
	}

	cout << size_y - count << endl;
}

int main(void)
{
	init();
	input();
	solve();
	output();

	return 0;
}