Official

B - Star or Not Editorial by sugarrr


グラフ理論の用語が急に出てきて戸惑った方もいたかと思うのですが、このレベルの単語はABCの中盤以降には注記無しで出てくると思うので、よければこの機会に覚えてみてください。


全ての頂点の次数(頂点から出ている辺の数のこと)を数えます。
次数が \(N-1\) の頂点があるなら答えは Yes 、ないなら答えは No です。

C++ の実装例を示します。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main(){
    ll n;cin>>n;
    vector<ll>count(n+1);//各頂点の次数を数える
    for(ll i=1;i<=n-1;i++){
        ll a,b;cin>>a>>b;
        count[a]++;
        count[b]++;
    }
    for(ll i=1;i<=n;i++){
        if(count[i] == n-1){
            cout<<"Yes"<<endl;
            return 0;//プログラムを終了する
        }
    }
    cout<<"No"<<endl;

    return 0;
}

posted:
last update: