2292.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2292 on 2006-07-26 at 02:41:34 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 51200;

class Node {
public:
	vector<int> n;
	bool vst, trap;
	int k, p;
	void make();
	void walk();
};
Node node[N];
void Node::make() {
	trap = vst = false; n.clear();
	int m, i; scanf("%d", &m);
	for(i = 0; i < m; i++) {
		int a; scanf("%d", &a);
		n.push_back(a-1);
	}
}
void Node::walk() {
	vst = true;
	if(trap) { k = 2; p = 0; return; }
	int i, o[2], on = 0;
	for(i = 0; i < n.size(); i++)
		if(n[i] >= 0 && !node[n[i]].vst) { o[on++] = n[i]; node[n[i]].walk(); }
	if(n.size() == 1) { k = 0; p = 1; }
	else if(n.size() == 2) { k = node[o[0]].k; p = node[o[0]].p; }
	else {
		if(node[o[0]].k && node[o[1]].k) { k = 2; p = node[o[0]].p+node[o[1]].p; }
		else if(!node[o[0]].k && !node[o[1]].k) { k = 0; p = 1; }
		else {
			k = 1; p = node[o[0]].p+node[o[1]].p;
			if(!node[o[0]].k) swap(o[0], o[1]);
			if(node[o[0]].k == 1) p--;
		}
	}
}

int main()
{
	int n, m, i;

	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		for(i = 0; i < n; i++) node[i].make();
		for(i = 0; i < m; i++) {
			int a; scanf("%d", &a);
			node[a-1].trap = true;
		}
		node[0].n.push_back(-1); node[0].walk();
		printf("%d\n", node[0].p);
	}
	
	return 0;
}