fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. vector<int> adj[200005];
  6. int daxet[200005], p[200005], mx, color[200005];
  7. int n;
  8.  
  9. void dfs(int v){
  10.     //cout << v << " ";
  11.     daxet[v] = 1;
  12.     int cl = 1;
  13.     for (int i = 0; i < adj[v].size(); i++){
  14.         if (!daxet[adj[v][i]]){
  15.         	p[adj[v][i]] = v;
  16. 			while(cl == color[v] || cl == color[p[v]]){
  17. 				cl++;
  18. 			}
  19.             color[adj[v][i]] = cl%(mx+1);
  20.             cl++;
  21.             dfs(adj[v][i]);
  22.         }
  23.     }
  24. }
  25.  
  26. int main(){
  27.     cin >> n;
  28.     int x, y;
  29.     for (int i = 1; i <= n-1; i++){
  30.         cin >> x >> y;
  31.         adj[x].push_back(y);
  32.         adj[y].push_back(x);
  33.     }
  34.     for (int i = 1; i <= n; i++){
  35. 		mx = max((int)adj[i].size(), mx);
  36. 	}
  37. 	mx++;
  38. 	color[1] = 1;
  39.     dfs(1);
  40.     cout << mx << endl;
  41.     for (int i = 1; i <= n; i++){
  42.         cout << color[i] << " ";
  43.     }
  44. }
Success #stdin #stdout 0s 23096KB
comments (?)
stdin
copy 
3
1 3
2 3
stdout
copy 
3
1 3 2
https://ideone.com/Z5HyHv
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!