比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAWWWWWW
题目名称 森林大礼包 最终得分 40
用户昵称 Sky_miner 运行时间 1.364 s
代码语言 C++ 内存使用 33.88 MiB
提交时间 2016-10-20 18:47:16
显示代码纯文本
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline ll cat_max(const ll &a,const ll &b){return a>b ? a:b;}
inline ll cat_min(const ll &a,const ll &b){return a<b ? a:b;}
const ll maxn = 100010;
const ll maxm = 1000010;
struct Edge{
	ll to,next;
}G[maxm<<1];
ll head[maxn],cnt,ind[maxn],num[maxn];
void add(ll u,ll v){
	G[++cnt].to = v;
	G[cnt].next = head[u];
	++ind[v];
	head[u] = cnt;
}
ll q[maxn],l,r=-1;
int main(){
	freopen("three_squirrels.in","r",stdin);
	freopen("three_squirrels.out","w",stdout);
	ll n;read(n);
	for(ll i=1,x,k;i<=n;++i){
		read(k);
		while(k--) read(x),add(x,i);
	}
	for(ll i=0;i<=n;++i) if(!ind[i]) q[++r] = i;
	num[0] = 1;
	while(l <= r){
		ll u = q[l++];
		for(ll i = head[u];i;i=G[i].next){
			num[G[i].to] += num[u];
			if(!(--ind[G[i].to])) q[++r] = G[i].to;
		}
	}
	printf("%lld",num[n]);
	//getchar();getchar();
	fclose(stdin);fclose(stdout);
	return 0;
}