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

दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम


मान लीजिए n वर्टेक्स और m एज वाला एक अनभारित, निदेश रहित ग्राफ दिया गया है। ग्राफ में एक ब्रिज एज वह एज है जिसे हटाने से ग्राफ असंबद्ध हो जाता है। हमें दिए गए ग्राफ में ऐसी एज की संख्या ज्ञात करनी है। ग्राफ में समानांतर एज या सेल्फ-लूप नहीं हैं।

उदाहरण के लिए, यदि इनपुट है n = 5, m = 6, edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}}, तो आउटपुट 1 होगा।

ग्राफ में केवल एक ब्रिज एज है जो {2, 4} है।

चरण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

mSize := 100
आकार mSize का सरणी G परिभाषित करें
एक 2D सरणी bridge परिभाषित करें
आकार mSize के सरणी visited, vk, l परिभाषित करें
पूर्णांक युग्मों वाला सरणी edges परिभाषित करें
एक फंक्शन depthSearch() परिभाषित करें जो v, p (डिफ़ॉल्ट -1) लेता है:
    visited[v] := 1
    vk[v] := l[v] := t++
    G[v] में प्रत्येक x के लिए:
        यदि x == p, तो जारी रखें
        यदि visited[x] सत्य है, तो:
            l[v] := min(l[v], vk[x])
        अन्यथा:
            depthSearch(x, v)
            l[v] := min(l[v], l[x])
            यदि l[x] > vk[v], तो:
                bridge[v][x] := 1
एक फंक्शन bridgeSearch() परिभाषित करें:
    t := 0
    i := 1 से n तक:
        यदि visited[i] असत्य है, तो:
            depthSearch(i)
i := 0 से m-1 तक:
    a := edges[i] का पहला मान
    b := edges[i] का दूसरा मान
    b को G[a] के अंत में डालें
    a को G[b] के अंत में डालें
bridgeSearch()
ans := 0
i := 1 से n तक:
    j := 1 से n तक:
        यदि i != j और bridge[i][j], तो:
            ans बढ़ाएँ
ans लौटाएँ

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; const int mSize = 100; vector <int> G[mSize]; int n, m, t; vector<vector<int>> bridge(mSize, vector<int>(mSize)); vector <int> visited(mSize); vector <int> vk(mSize, -1), l(mSize, -1); vector<pair<int, int>> edges; void depthSearch(int v, int p = -1) {    visited[v] = 1;    vk[v] = l[v] = t++;    for (auto x: G[v]) {       if (x == p) {          continue;       }       if (visited[x]) {          l[v] = min(l[v], vk[x]);       } else {          depthSearch(x, v);          l[v] = min(l[v], l[x]);          if (l[x] > vk[v]) {                bridge[v][x] = 1;          }       }    } } void bridgeSearch() {    t = 0;    for (int i = 1; i <= n; ++i) {       if (!visited[i]) {          depthSearch(i);       }    } } int solve(){    for (int i = 0; i < m; ++i) {       int a, b; a = edges[i].first;       b = edges[i].second;       G[a].push_back(b);       G[b].push_back(a);    }    bridgeSearch();    int ans = 0;    for (int i = 1; i <= n; ++i) {       for (int j = 1; j <= n; ++j) {          if (i != j and bridge[i][j]) ans++;       }    }    return ans; } int main() {    n = 5, m = 6;    edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}};    cout<< solve();    return 0; }

इनपुट

5, 6, {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}}

आउटपुट

1
  1. ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम ग्राफ में सुपर वर्टेक्स खोजने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स वाला एक ग्राफ दिया गया है। वर्टेक्स 1 से n तक संख्याबद्ध हैं और edges सरणी में दी गई एज्स से जुड़े हैं। प्रत्येक वर्टेक्स का एक x मान है जो 1 से n के बीच होता है, यह values सरणी में दिया गया है। हमें ग्राफ में सुपर वर्टेक्स खोजने हैं। एक वर्टेक्स i को सुपर वर्टेक्स कहा जाता है

  1. - दिए गए पूर्णांकों से अधिकतम संभावित टैली ज्ञात करने का C++ प्रोग्राम

    मान लीजिए हमें दो पूर्णांक n और m दिए गए हैं और k टपल्स हैं जिनमें चार पूर्णांक {ai, bi, ci, di} हैं। चार सरणियाँ a, b, c, d दी गई हैं जहाँ a[i] i-वें टपल का a मान दर्शाता है। अब एक अनुक्रम dp पर विचार करें जिसमें n धनात्मक पूर्णांक हों और 1 ≤ dp[1] < dp[2] < ... < dp[n] ≤ m। हम एक मेट्रिक टैली परि

  1. ग्रिड में रोशन सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम ग्रिड में रोशन सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए h × w आयाम का एक ग्रिड दिया गया है। ग्रिड की सेल्स में बल्ब या बाधाएँ हो सकती हैं। एक बल्ब सेल स्वयं और अपने दाएँ, बाएँ, ऊपर, नीचे की सेल्स को रोशन करता है। प्रकाश सेल्स के माध्यम से चमकता है जब तक कि कोई बाधा सेल इसे न रोक दे। बाधा सेल न तो रोशन हो सकती है और न ही प्रकाश को गुजरने देती ह