Solution for codeforces 403, div2C

codeforces_403_3.cpp

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

void dfs(vector<int>& colors, vector< list<int> >& adjlist, int cur, int parent) {
    int c = 1;
    for (int a : adjlist[cur]) {
        if (a != parent) {
            while (c == colors[cur] || c == colors[parent])
                ++c;
            colors[a] = c;
            ++c;
        }
    }

    for (int a : adjlist[cur])
        if (a != parent)
            dfs(colors, adjlist, a, cur);

}

int main(int, char**) {

    int n;
    cin >> n;
    vector< list<int> > adjlist(n+1);
    for (int i = 0; i < n-1; ++i) {
        int a,b;
        cin >> a >> b;

        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }

    vector<int> colors(n+1, 0);
    colors[1] = 1;
    dfs(colors, adjlist, 1, 0);

    cout << *max_element(colors.begin(), colors.end()) << "\n";
    for (int i = 1; i < n+1; ++i)
        cout << colors[i] << " ";
    cout <<"\n";

    return 0;
}