USACO 2019 February Contest Bronze Division - The Great Revegetation

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We will color each node one by one because there are at most 3 neighbors for each node so we can do it without having to worry about running out of colors.

Source codes

The source codes in C++ and Python can be seen below.

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

int n, m, color[101];

vector<vector<int> > graph;
int main()
{
    ifstream cin("revegetate.in");
    ofstream cout("revegetate.out");

    cin >> n >> m;
    graph.resize(n+1);

    for(int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int nr = 0;
    for(int i = 1; i <= n; i++)
    {
        set<int> freecolors = {1, 2, 3, 4};
        for(auto j : graph[i])
            if(color[j] != 0)
                freecolors.erase(color[j]);
        color[i] = *freecolors.begin();
        cout << color[i];
    }
    return 0;

}

with open("revegetate.in", "r") as fin:
    tokens = fin.read().split()
n = int(tokens[0])
m = int(tokens[1])
graph = [[] for _ in range(n+1)]
color = [0] * (n+1)
index = 2
for _ in range(m):
    a = int(tokens[index])
    b = int(tokens[index+1])
    index += 2
    graph[a].append(b)
    graph[b].append(a)
result = ""
for i in range(1, n+1):
    freecolors = {1, 2, 3, 4}
    for j in graph[i]:
        if color[j] != 0:
            freecolors.discard(color[j])
    color[i] = min(freecolors)
    result += str(color[i])
with open("revegetate.out", "w") as fout:
    fout.write(result)