โปรแกรม C++ หาจำนวนครั้งเฉลี่ยในการลบโหนดในกราฟทิศทาง

คำอธิบายปัญหา

สมมติว่าเรามีเมทริกซ์สมัยติดกันของกราฟทิศทาง G จนกว่ากราฟจะว่างเปล่า เราทำซ้ำการดำเนินการ: เลือกโหนดหนึ่งจาก G แล้วลบโหนดนั้นและโหนดทั้งหมดที่เข้าถึงได้จากโหนดนั้นโดยติดตามเส้นทาง การลบโหนดจะลบเส้นขอบที่เชื่อมด้วย ต้องการหาจำนวนครั้งเฉลี่ยที่ต้องดำเนินการ

ตัวอย่าง: กราฟ 3 โหนด ที่มีเส้นขอบตามภาพ ผลลัพธ์คือ 1.6667 เพราะ:

• เลือก A ลบทั้งหมด 1 ครั้ง
• เลือก B ลบ B และ C แล้วครั้งที่ 2 เลือก A ลบ A
• เลือก C คล้าย B ใช้ 2 ครั้ง
• ค่าเฉลี่ย = (1+2+2)/3 = 1.6667

ขั้นตอนการแก้ปัญหา

n := ขนาดของ G
สำหรับ i := 0 ถึง n-1: G[i,i] := 1
สำหรับ k := 0 ถึง n-1:
    สำหรับ i := 0 ถึง n-1:
        สำหรับ j := 0 ถึง n-1:
            ถ้า G[i,k] และ G[k,j] ไม่เป็นศูนย์: G[i,j] := 1
ans := 0
สำหรับ i := 0 ถึง n-1:
    k := 0
    สำหรับ j := 0 ถึง n-1:
        ถ้า G[j,i] ไม่เป็นศูนย์: เพิ่ม k ขึ้น 1
    ans := ans + 1.0 / k
คืนค่า ans

ตัวอย่างโค้ด C++

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

double solve(vector<vector<int>> G){
    int n = G.size();
    for (int i = 0; i < n; ++i) G[i][i] = 1;
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (G[i][k] && G[k][j])
                    G[i][j] = 1;
    double ans = 0;
    for (int i = 0; i < n; ++i){
        int k = 0;
        for (int j = 0; j < n; ++j)
            if (G[j][i]) ++k;
        ans += 1.0 / k;
    }
    return ans;
}

int main(){
    vector<vector<int>> G = { { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 }};
    cout << solve(G) << endl;
}

อินพุต

{ { 0, 1, 0 }, { 0, 0, 1 }, { 0, 1, 0 } }

เอาต์พุต

1.66667