นับจำนวนเส้นขอบในกราฟไม่มีทิศทางใน C++

งานคือนับจำนวนเส้นขอบ (edges) ในกราฟไม่มีทิศทาง (undirected graph) กราฟไม่มีทิศทางคือชุดของโหนด (vertices) ที่เชื่อมต่อกัน เส้นขอบทั้งหมดเป็นแบบสองทิศทาง

เส้นขอบในกราฟคือเส้นที่เชื่อมโหนดสองโหนดเข้าด้วยกัน

อินพุต − insert(graph_list, 0, 1); insert(graph_list, 0, 2); insert(graph_list, 1, 2); insert(graph_list, 1, 4); insert(graph_list, 2, 4); insert(graph_list, 2, 3); insert(graph_list, 3, 4);

เอาต์พุต − count of edges are: 7

แนวทาง

• สร้างรายการเก็บโหนดของกราฟ

• ฟังก์ชัน count_edges นับขนาดของแต่ละรายการติดกัน รวมแล้วหาร 2

ตัวอย่าง

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

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

void count_edges(list<int> graph_list[], int v){ 
    int count=0; 
    for (int i = 0; i < v; i++) count += graph_list[i].size(); 
    count = count/2; 
    cout<<"count of edges are: "<<count; 
} 

int main(){ 
    int vertices = 5; 
    list<int> graph_list[vertices]; 
    insert(graph_list, 0, 1); insert(graph_list, 0, 2); insert(graph_list, 1, 2); 
    insert(graph_list, 1, 4); insert(graph_list, 2, 4); insert(graph_list, 2, 3); insert(graph_list, 3, 4); 
    count_edges(graph_list, vertices); 
    return 0; 
}

เอาต์พุต

count of edges are: 7