Official

B - Star or Not Editorial by en_translator


You may be puzzled by the graph theory terms in the problem statement, but such basic terminologies will appear in intermediate problems or harder ones, so we recommend that you take this opportunity to remember them.


For each vertex, count its degree (the number of edges connected to the vertex).
If there is a vertex of degree \(N-1\), then the answer is Yes; otherwise the answer is No.

A sample code in C++ follows.

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

signed main(){
    ll n;cin>>n;
    vector<ll>count(n+1);//Counts the degree of each vertex
    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;//Terminates the program
        }
    }
    cout<<"No"<<endl;

    return 0;
}

posted:
last update: