এই টিউটোরিয়ালে, আমরা BIT ব্যবহার করে একটি রঙিন গাছের সাবট্রিতে স্বতন্ত্র রঙের সংখ্যা অনুসন্ধান করার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব।
এর জন্য আমাদেরকে রুটেড ট্রি দেওয়া হবে যেখানে প্রতিটি নোডের একটি রঙ প্রদত্ত অ্যারে দ্বারা চিহ্নিত করা হয়েছে। আমাদের কাজ হল গাছে প্রদত্ত নোডের নীচে সমস্ত স্বতন্ত্র রঙিন নোডগুলি খুঁজে বের করা৷
৷উদাহরণ
#include<bits/stdc++.h>
#define MAXIMUM_COLOUR 1000005
#define MAXIMUM_NUMBER 100005
using namespace std;
vector<int> tree[MAXIMUM_NUMBER];
vector<int> table[MAXIMUM_COLOUR];
int isTraversing[MAXIMUM_COLOUR];
int bit[MAXIMUM_NUMBER], getVisTime[MAXIMUM_NUMBER],
getEndTime[MAXIMUM_NUMBER];
int getFlatTree[2 * MAXIMUM_NUMBER];
bool vis[MAXIMUM_NUMBER];
int tim = 0;
vector< pair< pair<int, int>, int> > queries;
//storing results of each queryingTree
int ans[MAXIMUM_NUMBER];
void update(int idx, int val) {
while ( idx < MAXIMUM_NUMBER ) {
bit[idx] += val;
idx += idx & -idx;
}
}
int queryingTree(int idx) {
int result = 0;
while ( idx > 0 ) {
result += bit[idx];
idx -= idx & -idx;
}
return result;
}
void preformingDFS(int v, int color[]) {
//marking the node visited
vis[v] = 1;
getVisTime[v] = ++tim;
getFlatTree[tim] = color[v];
vector<int>::iterator it;
for (it=tree[v].begin(); it!=tree[v].end(); it++)
if (!vis[*it])
preformingDFS(*it, color);
getEndTime[v] = ++tim;
getFlatTree[tim] = color[v];
}
//adding an edge to the tree
void addingNewEdge(int u, int v) {
tree[u].push_back(v);
tree[v].push_back(u);
}
void markingFirstFind(int n) {
for (int i = 1 ; i <= 2 * n ; i++) {
table[getFlatTree[i]].push_back(i);
if (table[getFlatTree[i]].size() == 1) {
update(i, 1);
isTraversing[getFlatTree[i]]++;
}
}
}
void calcQuery() {
int j = 1;
for (int i=0; i<queries.size(); i++) {
for ( ; j < queries[i].first.first ; j++ ) {
int elem = getFlatTree[j];
update( table[elem][isTraversing[elem] - 1], -1);
if ( isTraversing[elem] < table[elem].size() ){
update(table[elem][ isTraversing[elem] ], 1);
isTraversing[elem]++;
}
}
ans[queries[i].second] = queryingTree(queries[i].first.second);
}
}
//counting distinct color nodes
void calcAllColours(int color[], int n, int qVer[], int qn) {
preformingDFS(1, color);
for (int i=0; i<qn; i++)
queries.push_back(make_pair(make_pair(getVisTime[qVer[i]] , getEndTime[qVer[i]]), i) );
sort(queries.begin(), queries.end());
markingFirstFind(n);
calcQuery();
for (int i=0; i<queries.size() ; i++) {
cout << "All distinct colours in the given tree: " << ans[i] << endl;
}
}
int main() {
int number = 6;
int color[] = {0, 2, 3, 3, 4, 1};
addingNewEdge(1, 2);
addingNewEdge(1, 3);
addingNewEdge(2, 4);
int queryVertices[] = {3, 2};
int qn = sizeof(queryVertices)/sizeof(queryVertices[0]);
calcAllColours(color, number, queryVertices, qn);
return 0;
} আউটপুট
All distinct colours in the given tree: 1 All distinct colours in the given tree: 2
