首页 > 代码库 > Codeforces Round #403 div2 C. Andryusha and Colored Balloons

Codeforces Round #403 div2 C. Andryusha and Colored Balloons

题目链接:Codeforces Round #403 div2 C. Andryusha and Colored Balloons

题意:

给你一棵n个节点的树,然后让你染色,规定相连的三个 节点不能同色,问需要的最少颜色,并输出其中一种方案。

题解:

因为只有相邻3个节点不同色。

所以直接DFS,每个节点都从1开始。

然后ans[v]!=ans[u]!=ans[fa]就行。

技术分享
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 const int N=2e5+7;
 6 int n,g[N],v[N*2],nxt[N*2],ed,cnt,ans[N];
 7 void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}
 8 
 9 void dfs(int x,int fa)
10 {
11     int cnt=1;
12     for(int i=g[x];i;i=nxt[i])if(v[i]!=fa)
13     {
14         while(cnt==ans[fa]||cnt==ans[x])cnt++;
15         ans[v[i]]=cnt,cnt++;
16     }
17     for(int i=g[x];i;i=nxt[i])if(v[i]!=fa)
18     {
19         dfs(v[i],x);
20     }
21 }
22 
23 int main(){
24     scanf("%d",&n);
25     int x,y;
26     F(i,1,n-1)
27     {
28         scanf("%d%d",&x,&y);
29         adg(x,y),adg(y,x);
30     }
31     ans[1]=1;
32     dfs(1,0);
33     int an=0;
34     F(i,1,n)an=max(an,ans[i]);
35     printf("%d\n",an);
36     F(i,1,n)printf("%d%c",ans[i]," \n"[i==n]);
37     return 0;
38 }
View Code

 

Codeforces Round #403 div2 C. Andryusha and Colored Balloons