➤ Problem Link : 780C. Andryusha and Colored Balloons
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int n;
vector<int> adj[200001];
int color[200001];
int k;
void dfs(int v, int c, int p)
{
int curr=1;
color[v]=c;
k=max(k,c);
for(int i=0;i<adj[v].size();i++)
{
if(adj[v][i]==p)
continue;
while(color[v]==curr || (p!=-1 && color[p]==curr))
curr++;
dfs(adj[v][i],curr,v);
curr++;
}
}
int main()
{
int x,y;
cin>>n;
for(int i=1;i<=n;i++)
adj[i].clear();
for(int i=1;i<=n-1;i++)
{
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
k=1;
dfs(1,1,-1);
cout<<k<<"\n";
for(int i=1;i<=n;i++)
cout<<color[i]<<" ";
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.