Codeforces Round #403 (Div. 2) C. Andryusha and Colored Balloons DFS

ProLightsfx 2017-3-20 158 3/20
C. Andryusha and Colored Balloons DFS

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

- THE END -
Tag:

ProLightsfx

11月17日01:35

最后修改:2024年11月17日
0

非特殊说明,本博所有文章均为博主原创,未经许可不得转载。

共有 0 条评论