2019计蒜之道初赛第一场 A 商汤的AI伴游小精灵（DFS）

Description

北京市商汤科技开发有限公司面向青少年研发了一款智能伴游机器人-- AI 伴游小精灵。一经推出，深受孩子们的喜爱，可爱又机智的小精灵会想出很多有趣的小游戏来启迪孩子们思考。今天，小精灵给你提出了一个神奇又有趣的多米诺骨牌小游戏。

你手上有一副神奇的多米诺骨牌，数量有 n 个，编号为 1∼n。它们之间存在着 n−1 个单向推倒关系，即推倒 x 会导致 y 也被推倒，而且这样的关系都满足 x<y，且每组关系中的 y 不会重复。

一开始只有 1 号骨牌不会被其他骨牌推倒，所以你只需要推倒 1 号骨牌就可以推倒所有的骨牌。

小精灵给你提的问题是：如果我们允许去掉 2 个骨牌，那么在最坏情况下你最少需要推倒几个骨牌才能使所有骨牌倒下？

输入格式

第一行输入一个整数 n，表示有 n 个多米诺骨牌。

接下来有 n-1 行的输入，每行输入两个整数 x,y，表示推倒 x 会导致 y 也被推倒。

输出格式

输出一个整数表示去掉两个骨牌之后，最坏情况下你最少需要推倒几个骨牌才能使所有骨牌倒下。

数据规模

n≤5×103

样例输入

7
1 2
1 3
1 5
2 4
4 7
4 6

样例输出

5

题意很清楚，第一感觉是找子节点最多的父节点，然后把这些子节点的父节点变为空，之后统计父节点为空的子节点有多少，但是这种情况对顺序排列的不适用。

应该先计算一个点的入度和出度，找到入度和出度和最大的那个点，作为第一个去掉的点，剩下的点，如果是指向它的点就把入度和出度的和-1，然后再找最大的点作为第二个点，去掉这两个点后再统计剩下的。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+7;
int a,b;
vector<int>mp[N];
bool vis[N];
struct node
{
    int id,cnt;
} out[N];
int cmp(node A,node B)
{
    if(A.cnt==B.cnt)
        return A.id>B.id;
    return A.cnt>B.cnt;
}
void dfs(int now,int f)
{
    vis[now] = 1;
    for(int i=0;i<mp[now].size();i++)
    {
        int v=mp[now][i];
        if(v<now||f==v||v==a||v==b||vis[v])
           continue;
        dfs(v,now);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        out[i].id=i;
    for(int i=0; i<n-1; i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        out[x].cnt++;//计算出度
        mp[x].push_back(y);
        mp[y].push_back(x);//统计前导点和后继点
    }
    if(n<=2)
        printf("%d\n",0);
    else
    {
        int ans=0;
        sort(out,out+n,cmp);
          a=1;
        if(out[0].id==1)
        {
            b=out[1].id;
        }
        else
            b=out[0].id;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&i!=a&&i!=b)
            {
                ans++;
                dfs(i,-1);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}