資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢可以在樹中斷開的邊數，使得生成的兩個樹的按位或相等
概念
對於給定的一棵具有 m 個節點的樹，每個節點都關聯一個數字，我們可以斷開任何樹邊，這將導致形成 2 棵新樹。在這裡，我們必須以這種方式計算邊的數量，以便在斷開該邊後構造的兩棵樹中存在的節點的按位或相等。需要注意的是，每個節點的值都 ≤ 10^6。
輸入
values[]={1, 3, 1, 3}
1
/ | \
2 3 4輸出
2
這裡，可以在 1 和 2 之間的邊斷開，生成的兩個樹的按位或將為 3。
同樣，也可以斷開 1 和 4 之間的邊。
方法
這裡，上述問題可以透過實現簡單的深度優先搜尋 (DFS) 來解決。因為節點的值 ≤ 10^6，所以可以使用 22 個二進位制位來表示。因此，節點值的按位或也可以用 22 個二進位制位來表示。這裡，方法是確定在子樹的所有值的每個位中設定位的次數。對於每條邊，我們將驗證從 0 到 21 的每個位，具有該特定位設定為 1 的數字在兩棵生成的樹中均為零或在兩棵生成的樹中均大於零，如果發現所有位都滿足該條件，則將該邊計入結果中。
示例
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
int m1[1000],x1[22];
// Uses array to store the number of times each bit
// is set in all the values of a subtree
int a1[1000][22];
vector<vector<int>> g;
int ans1 = 0;
// Shows function to perform simple DFS
void dfs(int u1, int p1){
for (int i=0;i<g[u1].size();i++) {
int v1 = g[u1][i];
if (v1 != p1) {
dfs(v1, u1);
// Determining the number of times each bit is set
// in all the values of a subtree rooted at v
for (int i = 0; i < 22; i++)
a1[u1][i] += a1[v1][i];
}
}
// Verifying for each bit whether the numbers
// with that particular bit as set are
// either zero in both the resulting trees or
// greater than zero in both the resulting trees
int pp1 = 0;
for (int i = 0; i < 22; i++) {
if (!((a1[u1][i] > 0 && x1[i] - a1[u1][i] > 0)
|| (a1[u1][i] == 0 && x1[i] == 0))) {
pp1 = 1;
break;
}
}
if (pp1 == 0)
ans1++;
}
// Driver code
int main(){
// Number of nodes
int n1 = 4;
// int n1 = 5;
// Uses ArrayList to store the tree
g.resize(n1+1);
// Uses array to store the value of nodes
m1[1] = 1;
m1[2] = 3;
m1[3] = 1;
m1[4] = 3;
/* m1[1] = 2;
m1[2] = 3;
m1[3] = 32;
m1[4] = 43;
m1[5] = 8;*/
//Uses array to store the number of times each bit
// is set in all the values in complete tree
for (int i = 1; i <= n1; i++) {
int y1 = m1[i];
int k1 = 0;
// Determining the set bits in the value of node i
while (y1 != 0) {
int p1 = y1 % 2;
if (p1 == 1) {
x1[k1]++;
a1[i][k1]++;
}
y1 = y1 / 2;
k1++;
}
}
// push_back edges
g[1].push_back(2);
g[2].push_back(1);
g[1].push_back(3);
g[3].push_back(1);
g[1].push_back(4);
g[4].push_back(1);
//g[1].push_back(5);
//g[5].push_back(1);
dfs(1, 0);
cout<<(ans1);
}輸出
2
更新於: 2020-07-25
258 次檢視
廣告