题解：P1700 [USACO19OPEN] Milk Factory B

· · 题解

结论题。看了下题解区，清一色的都是 O(n^2) 的搜索做法。这里我来介绍一种 O(n) 的做法。

首先注意到题目中的特殊性质，有 n-1 条通道，可以看出这就是一棵树。接着考虑树的性质。先假设有解，而且将答案点转化为根节点，如下图：

可以发现答案点的出度为 0，其它点的出度为 1，入度对答案没有影响。对于一个点的出度大于 1 的情况就判为无解，然后枚举每一个点，如果改点出度为 0 则直接输出并退出。

如果有大佬发现了漏洞请在评论区中 HACK 我这个蒟蒻（逃~

Code

#include <bits/stdc++.h>
using namespace std;
int n,x,y,out[101];
signed main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
        scanf("%d%d",&x,&y),out[x]++;
    for(int i=1;i<=n;i++)
        if(out[i]>1)
        {
            puts("-1");
            return 0;
        }
    for(int i=1;i<=n;i++)
        if(out[i]==0)
        {
            printf("%lld",i);
            return 0;
        }
    return 0;
}

END