AcWing 1738. 蹄球（特殊基环树）

题目链接

https://www.acwing.com/problem/content/description/1740/

思路

经过分析我们发现，对于每一个点来说，我们有至多两个入度以及必定有一个出度，那么这个图最终一定会构成一个基环图，而且是特殊的基环图，对于这个特殊的基环图，我们细分下来其实只有两种，一种是仅由两个点构成的环，并且没有其他入度，那么对于这个环图，我们只需要给其中的一个牛牛踢球就好了，如果是环上还由其他的入度，说明这个环挂了一个树，那么对于这样一个树，我们至少需要这棵树的所有叶子节点的元素，也就是入度为0的点的个数，对于前者我们计算每一个点的权值为1，后者我们计算每一个点的权值为2那么最后将所有满足条件的点的权值加上除二就好了 对于前者的图：

对于后者的图：

代码

#include
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e2+10;
int du[N],n,a[N],fa[N];

int main()
{
    cin>>n;
    for(int i = 1;i >a[i];
    sort(a+1,a+1+n);
    a[0] = -INF,a[n+1] = INF;
    
    for(int i = 1;i