1992.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 1992 on 2006-11-10 at 21:45:03 */
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N = 10240;
const int L = 64;
 
struct cmp {
	bool operator ()(const char* s1, const char* s2) const
		{ return strcmp(s1, s2) < 0; }
};
 
char ps[N][L], aval[N][L], str[L];
int pn, an, d[N];
vector<int> g[N], pg[N];
map<char*, int, cmp> pkg, av;
bool can[N];
 
int find(char*);
int avo(int);
 
int main()
{
	
	for(pn = an = 0; scanf("%s", aval[an]) == 1; an++) {
		av[aval[an]] = an;
		while(true) {
			scanf("%s", str);
			if(!strcmp(str, "0")) break;
			int ro = find(str);
			g[an].push_back(ro);
		}
	}
	memset(d, 0, sizeof(d)); memset(can, true, sizeof(can));
	for(int i = 0; i < an; i++)
		for(int j = g[i].size()-1; j >= 0; j--) {
			int no = avo(g[i][j]);
			if(no == -1) { can[i] = false; break; }
			else { d[i]++; pg[no].push_back(i); }
		}
	int istn = 0, stack[N], top = 0;
	for(int i = 0; i < an; i++)
		if(d[i] == 0 && can[i]) { stack[top++] = i; istn++; }
	while(top != 0) {
		int k = stack[--top];
		for(int i = pg[k].size()-1; i >= 0; i--) {
			int no = pg[k][i];
			d[no]--;
			if(d[no] == 0 && can[no]) { stack[top++] = no; istn++; }
		}
	}
	printf("%d\n", istn);
 
	return 0;
}
 
int find(char* s)
{
	if(!pkg.count(s)) {
		strcpy(ps[pn], s);
		pkg[ps[pn]] = pn;
		pn++;
	}
	return pkg.find(s)->second;
}
int avo(int k)
{
	if(!av.count(ps[k])) return -1;
	else return av.find(ps[k])->second;
}