Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में वेटेड पाथ वाले ग्राफ में सच्ची क्वेरीज की संख्या गिनने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास एक अनडायरेक्टेड ग्राफ के लिए एज लिस्ट है जहां प्रत्येक एज में [u, v, w] फील्ड होते हैं, u और v स्रोत और गंतव्य वर्टेक्स हैं और w वजन है। और क्वेरीज की एक सूची भी उसी फॉर्म [u, v, w] में है। जो इस प्रश्न को दर्शाता है कि क्या u और v के बीच एक पथ मौजूद है जैसे कि पथ में प्रत्येक एज का वजन अधिकतम w हो। तो सच्ची क्वेरीज की संख्या ढूंढें।

उदाहरण के लिए, यदि इनपुट है edges = [[0, 1, 6], [1, 2, 7], [2, 3, 8], [0, 3, 5]] queries = [[0, 2, 14], [1, 0, 3]]

C++ में वेटेड पाथ वाले ग्राफ में सच्ची क्वेरीज की संख्या गिनने का प्रोग्राम

तो आउटपुट 1 होगा, क्योंकि हम नोड 0 से 2 तक इस पथ [0, 1, 2] का अनुसरण करके वजन 13 के साथ जा सकते हैं। लेकिन 1 से 0 तक एज वजन 3 के साथ कोई पथ नहीं है।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम यूनियन-फाइंड (डिसजॉइंट सेट यूनियन) का उपयोग करेंगे:

  1. एक फंक्शन get_parent() परिभाषित करें जो x और par ऐरे लेता है
    • यदि par[x] != x, तो par[x] := get_parent(par[x], par)
    • par[x] वापस करें
  2. मुख्य विधि से:
    • एक 2D ऐरे gr परिभाषित करें
    • n := 0
    • edges में प्रत्येक एज t के लिए:
      • n := max(n, t[0], t[1])
      • gr में [t[2], 0, t[0], t[1]] पंक्ति डालें
    • queries में प्रत्येक क्वेरी t के लिए:
      • gr में [t[2], 1, t[0], t[1]] पंक्ति डालें
    • gr को सॉर्ट करें
    • आकार n+1 का एक ऐरे par परिभाषित करें और -1 से भरें
    • i := 0 से n तक: par[i] := i
    • sz := queries का आकार
    • ans := 0
    • gr में प्रत्येक पंक्ति t के लिए:
      • a := t[2], b := t[3], tp := t[1], d := t[0]
      • px := get_parent(a, par)
      • py := get_parent(b, par)
      • यदि tp == 0 (एज):
        • यदि px != py, तो par[py] := px
      • अन्यथा (क्वेरी):
        • यदि px == py, तो ans बढ़ाएं
        • sz घटाएं
        • यदि sz == 0, तो लूप से बाहर निकलें
    • ans वापस करें

उदाहरण

#include <bits/stdc++.h>
using namespace std;

int get_parent(int x, vector<int>& par) {
    if (par[x] != x) {
        par[x] = get_parent(par[x], par);
    }
    return par[x];
}

int solve(vector<vector<int>>& edges, vector<vector<int>>& queries) {
    vector<vector<int>> gr;
    int n = 0;
    for (auto t : edges) {
        n = max(n, max(t[0], t[1]));
        gr.push_back({t[2], 0, t[0], t[1]});
    }
    for (auto t : queries) {
        gr.push_back({t[2], 1, t[0], t[1]});
    }
    sort(gr.begin(), gr.end());
    vector<int> par(n + 1, -1);
    for (int i = 0; i <= n; i++) {
        par[i] = i;
    }
    int sz = queries.size();
    int ans = 0;
    for (auto t : gr) {
        int a = t[2];
        int b = t[3];
        int tp = t[1];
        int d = t[0];
        int px = get_parent(a, par);
        int py = get_parent(b, par);
        if (tp == 0) {
            if (px != py) {
                par[py] = px;
            }
        } else {
            if (px == py) {
                ans++;
            }
            sz--;
            if (sz == 0) {
                break;
            }
        }
    }
    return ans;
}

int main() {
    vector<vector<int>> edges = {{0, 1, 6}, {1, 2, 7}, {2, 3, 8}, {0, 3, 5}};
    vector<vector<int>> queries = {{0, 2, 14}, {1, 0, 3}};
    cout << solve(edges, queries);
}

इनपुट

{{0, 1, 6}, {1, 2, 7}, {2, 3, 8}, {0, 3, 5}}, {{0, 2, 14}, {1, 0, 3}}

आउटपुट

1
  1. - C++ प्रोग्राम में n-वर्ग के भाजक जो n के भाजक नहीं हैं

    इस ट्यूटोरियल में, हम एक प्रोग्राम लिखेंगे जो n-वर्ग के भाजकों की संख्या खोजता है न कि n के।यह एक सीधी समस्या है। समस्या को हल करने के चरण देखते हैं।संख्या n को इनिशियलाइज़ करें।भाजकों के लिए एक काउंटर इनिशियलाइज़ करें।2 से n² तक पुनरावृति करें।यदि n² वर्तमान संख्या से विभाज्य है और n वर्तमान संख्या

  1. - C++ में दिए गए GCD के बराबर उपसमुच्चयों की संख्या गिनें

    समस्या विवरण एक सरणी arr दी गई है जिसमें धनात्मक संख्याएं हैं और एक सरणी GCD[] जिसमें GCD मान हैं। लक्ष्य arr[] के तत्वों के उन उपसमुच्चयों की संख्या ज्ञात करना है जिनके GCD मान GCD[] में दिए गए हैं। उदाहरण इनपुट arr[] = {10, 5, 6, 3}, GCD[] = {2, 3, 5} आउटपुट दिए गए GCD के बराबर उपसमुच्चयों की सं

  1. C++ में डोमिनोज़ और ट्रोमिनोज़ से क्षेत्र भरने के कॉन्फिगरेशन की संख्या गिनने का प्रोग्राम C++ में डोमिनोज़ और ट्रोमिनोज़ से क्षेत्र भरने के कॉन्फिगरेशन की संख्या गिनने का प्रोग्राम

    परिचय मान लीजिए हमारे पास दो आकार हैं: डोमिनो (Domino) और ट्रोमिनो (Tromino)। डोमिनो 2×1 आकार के होते हैं और ट्रोमिनो L जैसे आकार के होते हैं। उन्हें नीचे दिखाए अनुसार घुमाया जा सकता है। यदि हमारे पास एक संख्या n है, तो हमें इन दो प्रकार के टुकड़ों से 2×n बोर्ड भरने के कॉन्फिगरेशन की संख्या ढूंढ