Hacker Rank: Kingdom Division 不完全报告

原题链接：

Kingdom Division

由于树的层次可能很深，所以这里不能使用递归版的DFS。我使用了BFS。
BFS确定各结点的父结点和它的孩子数。
用逆拓扑排序确定结点的计算顺序。
same[u][] 表示u结点颜色为0孩子结点颜色全为1时组合数。 diff[u][] 表示u结点颜色为0时可行组合数。本结点颜色为0，子结点颜色为1，孙结点颜色全为0是无效组合。反之亦然。由于这里颜色0、1相互对称， same[u][]=same[u][]; diff[u][]=diff[u][]; 。
为排除无效组合，计算 diff[u][] 时没有乘以 same[u][] 。
本结点为0，孩子结点全为1，是无效组合，因此 diff[u][] 最后还要减去 same[u][] 。

#include <cmath>

#include <cstdio>

#include <cassert>

#include <vector>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

const int MOD = 1e9+;

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */

    int n = ; assert( == scanf("%d", &n));

    vector<vector<int>> adjList(n + );

    for(int i = ; i < n - ; i++){

        int u, v; assert( == scanf("%d %d", &u, &v));

        adjList[u].push_back(v);

        adjList[v].push_back(u);

    }

    vector<vector<long long>>  diff(n + , vector<long long>(, ));

    vector<vector<long long>> same(n + , vector<long long>(, ));

    vector<int> parent(n + , );

    vector<int> child_cnt(n + , );

    queue<int> traversal_array;

    vector<bool> visited(n + , false);

    traversal_array.push();

    visited[] = true;

    while(!traversal_array.empty()){

        int tmp = traversal_array.front();

        traversal_array.pop();

        for(auto vit: adjList[tmp]){

            if(!visited[vit]){

                visited[vit] = true;

                child_cnt[tmp]++;

                parent[vit] = tmp;

                traversal_array.push(vit);

            }

        }

    }

    for(int c_i = ; c_i <= n; c_i++){

        if(!child_cnt[c_i]){

            traversal_array.push(c_i);

        }

    }

    while(!traversal_array.empty()){

        int tmp = traversal_array.front();

        traversal_array.pop();

        child_cnt[parent[tmp]]--;

        if(child_cnt[parent[tmp]] == ){

            traversal_array.push(parent[tmp]);

        }

        for(auto vit: adjList[tmp]){

            if(vit != parent[tmp]){

                same[tmp][] = same[tmp][] * diff[vit][] % MOD;

                same[tmp][] = same[tmp][] * diff[vit][] % MOD;

            }

        }

        for(auto vit: adjList[tmp]){

            if(vit != parent[tmp]){

                diff[tmp][] = diff[tmp][] * (diff[vit][] + diff[vit][] + same[vit][]) % MOD;

                diff[tmp][] = diff[tmp][] * (diff[vit][] + diff[vit][] + same[vit][]) % MOD;

            }

        }

        diff[tmp][] = (diff[tmp][] - same[tmp][] + MOD) % MOD;

        diff[tmp][] = (diff[tmp][] - same[tmp][] + MOD) % MOD;

    }

    printf("%lld\n", (diff[][] + diff[][])%MOD);

    return ;

}

巴特西

Hacker Rank: Kingdom Division 不完全报告

Kingdom Division

最新文章

热门文章