P9608 [CERC2019] Bob in Wonderland 题解

· · 题解

题意

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

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

思路

求这个链解开多少个环可以解成若干条直链，就是在求这个链有多少个环连了大于 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;
}