题解 | #[USACO 2010 Nov S]Chocolate Milk#

using namespace std;
const int N=100005;
int h[N],to[N],ne[N],cnt=1;//链式前向星
int inde[N],outde[N],q[N],ans[N];//入度，出度，队列模拟，记录到每个点时前面点的贡献
int head=0,tail=0;//队列首位
bool ismilk[N];
void add(int a,int b){
    to[cnt]=b;
    ne[cnt]=h[a];
    h[a]=cnt++;
    inde[b]++;
    outde[a]++;
}
void solve(){
    while(head<tail){
        int t=q[head++];
        if(outde[t]>1)continue;
        for(int i=h[t];i;i=ne[i]){
            int temp=to[i];
            ans[temp]=ans[temp]+ans[t];
            inde[temp]--;
            if(inde[temp]==0)q[tail++]=temp;
        }
    }
}
int main(){
    int n,ai,bi,incnt=0;
    cin>>n;
    memset(h,0,sizeof(h));
    memset(ismilk,false,sizeof(ismilk));
    for(int i=1;i<n;i++){
        cin>>ai>>bi;
        add(ai,bi);
    }
    for(int i=1;i<=n;i++){
        if(!inde[i]){
            incnt++;
            q[tail++]=i;
            ans[i]=1;
            ismilk[i]=true;
        }
    }
    solve();
    for(int i=1;i<=n;i++){
        if(ans[i]==incnt&&!ismilk[i]){
           cout<<i<<"\n";
        }
    }
}

本题目关键在于以下几点： 1.有向无环图 2.牛奶流向是从一个点到另一个点，有且只有一种路径，所以只要某节点分叉了，那么之后子节点一定不可能是混合器所在位置 3.混合器不能放在挤奶器（入度为零的点）

所以我们就有大致思路，对于抛去挤奶器的点，只要该点被所有挤奶器流过，那么就可以输出作为答案，本题牛奶都能流到奶槽里所以不用额外判断，是否能到达奶槽。挤奶器是源点，入度为零，所以可以用拓扑排序，通过一个ans数组来记录到当前点的累计贡献也就是有几个挤奶器的奶流过，最后判断ans数组里面是否有贡献点等于挤奶器数量，且不与挤奶器重复的点，从小到大输出即可。

链式前向星存图，遍历图，找到入度为0的点，打上标记，记录数量，数组模拟队列实现拓扑排序，这里有个关键剪枝对于出度大于1的点也就是分叉节点，其后的的点一定不可能是答案所以跳过；