USACO 2019 January Contest Silver Division - Grass Planting

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The main observation is that the minimum number of colors needed is the maximum number of connections a node has in the graph + 1, because all the connected points from a singular node have to be unique colors, including the node itself, in order to not be adjacently similar colored or semi adjacent, as the nodes connected to the vertex are semi-adjacent.

Source code

The source code in C++ can be seen below.

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

int main() {
    freopen("planting.in", "r", stdin);
    freopen("planting.out", "w", stdout);
    int N;
    cin >> N;
    vector<int> degree(N);
    int a, b;
    for (int i = 1; i < N; i++) {
        cin >> a >> b;
        degree[a - 1]++;
        degree[b - 1]++;
    }
    int result = 0;
    for (int i = 0; i < N; i++) {
        result = max(result, degree[i]);
    }
    cout << result + 1 << '\n';
    return 0;
}