题目名称：商汤的AI伴游小精灵
题目链接：商汤的AI伴游小精灵
描述
北京市商汤科技开发有限公司面向青少年研发了一款智能伴游机器人-- AI 伴游小精灵。一经推出，深受孩子们的喜爱，可爱又机智的小精灵会想出很多有趣的小游戏来启迪孩子们思考。今天，小精灵给你提出了一个神奇又有趣的多米诺骨牌小游戏。
你手上有一副神奇的多米诺骨牌，数量有 nnn 个，编号为 1∼n1 \sim n1∼n。它们之间存在着 n−1n-1n−1 个单向推倒关系，即推倒 xxx 会导致 yyy 也被推倒，而且这样的关系都满足 x<yx<yx<y，且每组关系中的 yyy 不会重复。
一开始只有 111 号骨牌不会被其他骨牌推倒，所以你只需要推倒 111 号骨牌就可以推倒所有的骨牌。
小精灵给你提的问题是：如果我们允许去掉 222 个骨牌，那么在最坏情况下你最少需要推倒几个骨牌才能使所有骨牌倒下？
输入
第一行输入一个整数 n，表示有 n 个多米诺骨牌。
接下来有 n−1行的输入，每行输入两个整数 x,y，表示推倒 x 会导致 y 也被推倒。
输出
输出一个整数表示去掉两个骨牌之后，最坏情况下你最少需要推倒几个骨牌才能使所有骨牌倒下。
样例输入
7 1 2 1 3 1 5 2 4 4 7 4 6
样例输出
5
解题思路
利用C++中STL函数库里的vector生成邻接链表，使用sort函数按照x出现次数的最大值进行排序，使用degree标注该处是否被推倒，第一次遍历所有数据得出需要剔除两个骨牌，接下来利用拓扑排序统计需要推到的次数即可
代码如下
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define N 5010
int n;
int x,y;
int degree[N];
vector<int>V[N];
struct Node{
int v,t;
}node[N];
bool cmp(Node a,Node b){
return a.t>b.t;
}
void init(){
for(int i=1;i<=n;i++) degree[i]=1;
}
void dfs(int index){
for(int i=0;i<V[index].size();i++){
int u=V[index][i];
if(u==node[1].v||u==node[2].v) continue;
degree[u]=0;
dfs(u);
}
}
int main()
{
cin>>n;
init();
for(int i=1;i<n;i++){
cin>>x>>y;
V[x].push_back(y);
node[x].t++;
node[x].v=x;
}
sort(node+1,node+1+n,cmp);
int ans=0;
for(int i=1;i<=n;i++){
if(i!=node[1].v&&i!=node[2].v){
if(degree[i]==1){
dfs(i);
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
