题意：对于n个顶点，n-1条边的图形，给n个点染色，每连续的3点的颜色不相同，求需要最小颜色数量，并给出染色情况。
最小颜色数量其实，为 min(点的度+1）。对于某点i染色来说，记录i前的颜色，i的颜色，i相邻的点的颜色和前两者不相同。
#include<bits/stdc++.h>using namespace std;vector<int> G[200005];int col[200005],par[200005];int main(){ int n;scanf("%d",&n); for(int i=1;i<n;i++) { int x,y;scanf("%d%d",&x,&y); G[x].push_back(y); G[y].push_back(x); } queue<int> Q; col[1]=1; par[1]=1; Q.push(1); int k = -1; while(!Q.empty()) { int node = Q.front(); Q.pop(); int num = 1; for(int i=0;i<G[node].size();i++) { if(!col[ G[node][i] ]) { if(col[node] == num || col[ par[node] ] == num) num++; if(col[node] == num || col[ par[node] ] == num) num++; col[ G[node][i] ] = num; k = max(k,num); par[ G[node][i] ] = node; num++; Q.push(G[node][i]); } } } PRintf("%d/n",k); for(int i=1;i<=n;i++) { printf("%d ",col[i]); } printf("/n"); return 0;}新闻热点
疑难解答
