自动搬运

查看原文

来自洛谷，原作者为

	Defy_HeavenS 世界上有两种程序员，一种是下标以0开始的，一种是下标以1开始的，我是第一种，请问我是下标为几的程序员

搬运于2025-08-24 22:50:05，当前版本为作者最后更新于2023-09-09 14:18:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给你一个由若干个环相扣而成的链条，如果想让这个链条变成直链，至少要解开几个环。

直链是指每个环最多和其他两个环相扣的链，如：

思路

求这个链解开多少个环可以解成若干条直链，就是在求这个链有多少个环连了大于 $2$ 个其他环，只要把这些连接数量大于 $2$ 的解开就是若干条直链。

比如一个环和 $3$ 个环相扣，就要解开 $1$ 个。

那么怎么求有几个连接数量大于 $2$ 的环呢？

我们看题，在直链中，每个环最多连接两个其他环，那么把链想象成无向图就是每个顶点的度不能大于 $2$，如果大于 $2$ 就要断开其他的顶点。

还是上面那个例子，最大的环的度是 $3$，就要断开 $3-2$ 个环。

代码

#include<bits/stdc++.h>
using namespace std;
int n,u,v,s;
int d[300005];
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		d[u]++,d[v]++;
	}
	for(int i=1;i<=n;i++){
		if(d[i]>2){
			s+=max(0,d[i]-2);
		}
	}
	cout<<s;
	return 0;
}