Cari bilangan nod sinki dalam graf menggunakan C++

Dalam artikel ini, kami akan menerangkan maklumat penting untuk menyelesaikan bilangan nod sinki dalam graf. Dalam masalah ini, kita mempunyai graf asiklik terarah dengan nod N (1 hingga N) dan tepi M. Matlamatnya adalah untuk mengetahui berapa banyak nod sinki yang terdapat dalam graf tertentu. Nod sink ialah nod yang tidak menghasilkan sebarang tepi keluar. Berikut ialah contoh mudah -

Input : n = 4, m = 2

Edges[] = {{2, 3}, {4, 3}}
Output : 2

Cara mudah untuk mencari penyelesaian

Dalam pendekatan ini, kita akan melintasi tepi graf dan menambah set yang ditunjuk oleh tepi. elemen yang berbeza ditolak ke dalamnya dan kemudian saiz set ditolak daripada jumlah bilangan nod yang ada.

Contoh

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n = 4; // number of nodes.
    int m = 2; // number of edges.
    vector<pair<int, int>> edges = {{2, 3}, {4, 3}}; // the edges going from first to second.
    set<int> s;
    for(int i = 0; i < m; i++){
        s.insert(edges[i].first); // will keep value of
                               // distinct node from which edges are going out.
    }
    cout << n - s.size(); // answer is the total number of nodes - number of non sink nodes.
    return 0;
}

Output

2

Penerangan kod di atas

O(N), dengan N mewakili bilangan tepi yang terdapat dalam graf.

Atas ialah kandungan terperinci Cari bilangan nod sinki dalam graf menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!