数据结构的作用就很好的体现在这道题目上

题目来源:https://nanti.jisuanke.com/t/39260

题目描述
北京市商汤科技开发有限公司面向青少年研发了一款智能伴游机器人– AI 伴游小精灵。一经推出，深受孩子们的喜爱，可爱又机智的小精灵会想出很多有趣的小游戏来启迪孩子们思考。今天，小精灵给你提出了一个神奇又有趣的多米诺骨牌小游戏。
你手上有一副神奇的多米诺骨牌，数量有 n 个，编号为 1∼n。它们之间存在着 n−1 个单向推倒关系，即推倒 x 会导致 y 也被推倒，而且这样的关系都满足 x < y, 且每组关系中的 y 不会重复。
一开始只有 1 号骨牌不会被其他骨牌推倒，所以你只需要推倒 1 号骨牌就可以推倒所有的骨牌。
小精灵给你提的问题是：如果我们允许去掉 2 个骨牌，那么在最坏情况下你最少需要推倒几个骨牌才能使所有骨牌倒下？
输入格式
第一行输入一个整数 n，表示有 n 个多米诺骨牌。
接下来有 n-1 行的输入，每行输入两个整数 x,y，表示推倒 x 会导致 y 也被推倒。
输出格式
输出一个整数表示去掉两个骨牌之后，最坏情况下你最少需要推倒几个骨牌才能使所有骨牌倒下。
数据规模
$n \le 5 \times 10^3$
样例输入
7
1 2
1 3
1 5
2 4
4 7
4 6
样例输出
5

题目分析

• 输入的每组x,y就是将两个节点相连，由此组成一棵树；
• 从任一节点向下遍历，便是进行“推倒骨牌”，如果从根结点开始“推倒”，一次便可将所有“骨牌推倒”；
  也就是对于一棵树，最少“推导”一个骨牌便可使所有骨牌“倒下”；
• 题目要求“去掉两个”，即删除两个节点，变成森林；
  “最坏情况”，即问该森林最多有多少棵树；

算法分析
只需删除出度最大的两个节点即可

————————————————完整代码————————————————————

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef struct{
	int n;
	int link;
}node;
node a[5005];
int m[5005][5005];
int n;
bool comp(node x, node y){
	return x.n > y.n;
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		a[i].link = i;
	for(int i = 1; i < n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		m[x][y] = 1;
		a[x].n++;	
	}
	sort(a+1, a+n+1, comp);
	node l1 = a[1], l2 = a[2];//取出度最大的两节点
	int maxn = l1.n + l2.n + 1;
	if(a[1].link == 1 || a[2].link == 1)//若某一个为根节点
		maxn--;
	if(m[l1.link][l2.link] == 1)//若两节点相连
		maxn--;
	printf("%d\n", maxn);
	return 0;
}