【luoguP2999】 [USACO10NOV]巧克力牛奶Chocolate Milk

题目链接

考虑每条路径都经过的一个点，它可以到达每个出度为零点（终点），且每个入读为零点（起点）都能到达它，

拓扑排序记录下每个结点能到达的出度为零点的个数和沿反边能到达的入读为零点个数，判断是否等于总个数即可

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int MAXN=100010;
const int MAXM=400010;

int n;
int Head[MAXN],num,du[MAXN],cnt1,f1[MAXN];
int _Head[MAXN],_num,_du[MAXN],cnt2,f2[MAXN];

struct Edge{
	int to,nxt;
}e[MAXN],_e[MAXN];

inline void add(int x,int y){
	e[++num].to=y;
	e[num].nxt=Head[x];
	Head[x]=num;
}
inline void _add(int x,int y){
	_e[++_num].to=y;
	_e[_num].nxt=_Head[x];
	_Head[x]=_num;
}

int dfs1(int x){
	if(f1[x]) return f1[x];
	int sum=0;
	if(du[x]==0) ++sum;
	for(int i=Head[x];i;i=e[i].nxt){
		int to=e[i].to;
		sum+=dfs1(to);
	}
	return f1[x]=sum;
}

int dfs2(int x){
	if(f2[x]) return f2[x];
	int sum=0;
	if(_du[x]==0) ++sum;
	for(int i=_Head[x];i;i=_e[i].nxt){
		int to=_e[i].to;
		sum+=dfs2(to);
	}
	return f2[x]=sum;
}

int main()
{
	scanf("%d",&n);
	int x,y;
	for(int i=1;i<n;++i){
		scanf("%d%d",&x,&y);
		add(x,y); ++du[x];
		_add(y,x); ++_du[y];
	}
	for(int i=1;i<=n;++i){
		if(du[i]==0) ++cnt1;
		if(_du[i]==0) ++cnt2;
	}
	for(int i=1;i<=n;++i)
		if(!f1[i]) dfs1(i);
	for(int i=1;i<=n;++i)
		if(!f2[i]) dfs2(i);
	for(int i=1;i<=n;++i)
		if(_du[i]!=0&&f1[i]==cnt1&&f2[i]==cnt2)
			printf("%d
",i);
	return 0;
}