C++ में अनिर्देशित ग्राफ (Undirected Graph) में किनारों (edges) की गिनती

समस्या विवरण

एक अनिर्देशित ग्राफ (undirected graph) दिया गया है। हमें ग्राफ में कुल किनारों (edges) की संख्या गिननी है। अनिर्देशित ग्राफ में सभी किनारे द्विदिश (bidirectional) होते हैं।

दृश्य प्रतिनिधित्व

उदाहरण

इनपुट

किनारे: (0,1), (0,2), (1,2), (1,4), (2,4), (2,3), (3,4)

आउटपुट

किनारों की संख्या: 7

समाधान दृष्टिकोण

सन्निकटता सूची (adjacency list) में, प्रत्येक किनारा दो बार गिना जाता है (एक बार प्रत्येक शीर्ष के लिए)। इसलिए:

कुल_किनारे = (सभी शीर्षों के आसन्न सूची आकारों का योग) / 2

कार्यकारी प्रोग्राम

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

void insertEdge(list<int> adj[], int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void countEdges(list<int> adj[], int V) {
    int count = 0;
    for (int i = 0; i < V; i++) {
        count += adj[i].size();
    }
    count /= 2; // प्रत्येक किनारा दो बार गिना गया
    cout << "किनारों की संख्या: " << count;
}

int main() {
    int V = 5;
    list<int> adj[V];
    
    insertEdge(adj, 0, 1);
    insertEdge(adj, 0, 2);
    insertEdge(adj, 1, 2);
    insertEdge(adj, 1, 4);
    insertEdge(adj, 2, 4);
    insertEdge(adj, 2, 3);
    insertEdge(adj, 3, 4);
    
    countEdges(adj, V);
    return 0;
}

आउटपुट

किनारों की संख्या: 7