इस ट्यूटोरियल में, हम 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; //क्वेरी के परिणाम संग्रहीत करना 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[]) { //नोड को विजिटेड मार्क करना 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]; } //ट्री में एज जोड़ना 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); } } //अलग-अलग रंग के नोड्स गिनना 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
