題意：對于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]); } } }新聞熱點
疑難解答
