My Solution
题意:给出一颗无根树,要求如果a-b相连 b-c相连,则要求abc涂上不同的颜色,要求用最少的颜色给这颗树上色且求具体涂色。
DFS
首先这个最少的颜色数必定是 最大度+1,
然后具体涂色的时候可以dfs来涂色,因为dfs的时候孙子节点的颜色只跟相应子节点和父节点有关,跟该父节点的其它子节点没有关系,
所以用dfs来涂色。
复杂度 O(n)
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 8;
vector sons[maxn];
int p[maxn];
void dfs(const int &g, const int &u)
{
int j, sz, ptr = 1;
sz = sons[u].size();
if(sz == 1) return;
for(j = 0; j < sz; j++){ while(ptr == p[g] || ptr == p[u]) ptr++; if(sons[u][j] == g) continue; p[sons[u][j]] = ptr; ptr++; dfs(u, sons[u][j]); } } int main() { #ifdef LOCAL freopen("c.txt", "r", stdin); //freopen("c.out", "w", stdout); int T = 4; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int n, v, u, t, ans = 0, i, j, sz, maxi; cin >> n; t = n - 1;
while(t--){
cin >> u >> v;
sons[u].push_back(v);
sons[v].push_back(u);
}
for(i = 1; i <= n; i++){
sz = sons[i].size();
if(ans < sz + 1){
ans = sz + 1;
maxi = i;
}
}
p[maxi] = ans; p[0] = 0;
dfs(0, maxi);
cout << ans << "n" << p[1];
for(i = 2; i <= n; i++) cout << " " << p[i];
#ifdef LOCAL
for(int i = 1; i <= n; i++){
sons[i].clear();
}
memset(p, 0, sizeof p);
cout << endl;
}
#endif // LOCAL
return 0;
}
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
https://www.prolightsfxjh.com/
Thank you!
------from ProLightsfx
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
如经许可后转载,请注明出处:https://prolightsfxjh.com/article/codeforces-round-403-div-2-c-andryusha-and-colored-balloons-dfs/
共有 0 条评论