【JZOJ 4269】【NOIP2015模拟10.27】挑竹签

题目大意:

(n) 个竹签,只能拿走没被压着的竹签,问最多能拿走多少个竹签。

正文:

由题目大意可以看出此题是拓扑排序的板子题。

代码:

int main()
{
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		scanf ("%d%d", &u, &v);
		fathernum[v] ++;
		Add(u, v);
	}
	int h = 0, t = 0;
	for (int i = 1; i <= n; i++)
		if(!fathernum[i])
			start[++t] = i, vis[i] = 1;
	while(h <= t)
	{
		h++;
		for (int i = head[start[h]]; i; i = e[i].next)
		{
			int v = e[i].to;
			fathernum[v] --;
			if(!fathernum[v] && !vis[v])
			{
				vis[v] = 1;
				start[++t] = v;
			}
		 } 
	}
	printf("%d", t);
    return 0;
}

原文地址:https://www.cnblogs.com/GJY-JURUO/p/13465355.html